Omega-regulär

Omega-regulär

In der theoretischen Informatik bezeichnet eine ω-reguläre Sprache eine Menge unendlicher Wörter über einem gemeinsamen Alphabet, die gewissen Gesetzmäßigkeiten genügt. Im Fall von endlichen Wörtern heißt das Äquivalent reguläre Sprache.

Häufig wird diese Sprachklasse in der Automatentheorie genutzt. Die ω-reguläre Sprachen akzeptierenden Automaten heißen ω-Automaten.

Unendliche Wörter

Ein unendliches Wort ist eine unendliche Sequenz von Zeichen aus einem Alphabet. Man kann dies über eine Abbildung mithilfe der natürlichen Zahlen {\N} formalisieren, bei der jeder Position im Wort der dort befindliche Buchstabe zugewiesen wird. Über dem Alphabet {0,1} kann z.B. das unendliche Wort 0101111111\ldots gebildet werden.

Die Menge der unendlichen Wörter über einem Alphabet Σ wird mit Σω bezeichnet. Teilmengen aus Σω heißen ω-Sprachen.

Definition

Seien Σ ein endliches Alphabet, U \subseteq \Sigma^* eine reguläre Sprache und L_1,L_2 \subseteq \Sigma^{\omega} zwei ω-reguläre Sprachen, dann gilt:

  • Uω ist eine ω-reguläre Sprache
  • U \cdot L_1 ist eine ω-reguläre Sprache
  • L_1 \cup L_2 und L_1 \cap L_2 sind ω-reguläre Sprachen.

Mit dieser Vorschrift können alle ω-regulären Sprachen konstruiert werden.

Die ω-regulären Sprachen sind genau die büchi-erkennbaren Sprachen.


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Omega-regular language — The ω regular languages are a class of ω languages which generalize the definition of regular languages to infinite words. Büchi showed in 1962 that ω regular languages are precisely the ones definable in a particular monadic second order logic… …   Wikipedia

  • Regular conditional probability — is a concept that has developed to overcome certain difficulties in formally defining conditional probabilities for continuous probability distributions. It is defined as an alternative probability measure conditioned on a particular value of a… …   Wikipedia

  • Omega Rojo — Primera aparición X Men (Vol. 2) #4 (1992) Marvel Comics Creador(es) Jim Lee y John Byrne Información Nombre original …   Wikipedia Español

  • Omega Chess — is a commercial chess variant designed by Daniel MacDonald in Toronto. The game is played on a 10x10 board with an extra square in each of the extreme corners where the wizards are placed at the start of the game.[1] The game is laid out like… …   Wikipedia

  • Omega (relojería) — Omega SA Tipo Privada Fundación 1848 …   Wikipedia Español

  • Omega Epsilon Sigma — was a collegiate sorority operating in the United States from 1925 until, approximately, 1930. This sorority is the second known organization for college women with Order of the Eastern Star affiliation. (The first sorority being Achoth.)… …   Wikipedia

  • Regular cardinal — In set theory, a regular cardinal is a cardinal number that is equal to its own cofinality. So, crudely speaking, a regular cardinal is one which cannot be broken into a smaller collection of smaller parts.(The situation is slightly more… …   Wikipedia

  • Omega-3 fatty acid — For an explanation of n and numerical nomenclature (such as n−3 or 18:3), see Fatty acid#Nomenclature. Types of fats in food Unsaturated fat Monounsaturated fat Polyunsaturated fat Trans fat Cis fat Omega fatty acids: ω−3 ω−6 ω−9 Saturated fat… …   Wikipedia

  • Omega Red — This article is about the Marvel comic book character. For the musician, see Omega Red (musician). Omega Red Omega Red, as depicted on the cover of X Men #18 (vol. 2, March 1993). Art by Andy Kubert …   Wikipedia

  • Omega and agemo subgroup — In mathematics, or more specifically group theory, the omega and agemo subgroups described the so called power structure of a finite p group. They were introduced in (Hall 1933) where they were used to describe a class of finite p groups whose… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”