ω-regulär

ω-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:

  • Regular Baptist — Regular Baptists are a diverse group of Baptists in the United States and Canada. The presence of the modifier Regular in their names attests to the strong influence of the early Regular Baptists on the growth of Baptists in North America. Two… …   Wikipedia

  • regular — verbo transitivo 1. Poner (una persona) [una cosa] en orden o en estado de normalidad: Un guardia regula la circulación del cruce. Sinónimo: organizar. 2. Determinar ( …   Diccionario Salamanca de la Lengua Española

  • Regular — Reg u*lar ( l?r), a. [L. regularis, fr. regula a rule, fr. regere to guide, to rule: cf. F. r[ e]gulier. See {Rule}.] [1913 Webster] 1. Conformed to a rule; agreeable to an established rule, law, principle, or type, or to established customary… …   The Collaborative International Dictionary of English

  • Regular polygon — Regular Reg u*lar ( l?r), a. [L. regularis, fr. regula a rule, fr. regere to guide, to rule: cf. F. r[ e]gulier. See {Rule}.] [1913 Webster] 1. Conformed to a rule; agreeable to an established rule, law, principle, or type, or to established… …   The Collaborative International Dictionary of English

  • Regular polyhedron — Regular Reg u*lar ( l?r), a. [L. regularis, fr. regula a rule, fr. regere to guide, to rule: cf. F. r[ e]gulier. See {Rule}.] [1913 Webster] 1. Conformed to a rule; agreeable to an established rule, law, principle, or type, or to established… …   The Collaborative International Dictionary of English

  • Regular sales — Regular Reg u*lar ( l?r), a. [L. regularis, fr. regula a rule, fr. regere to guide, to rule: cf. F. r[ e]gulier. See {Rule}.] [1913 Webster] 1. Conformed to a rule; agreeable to an established rule, law, principle, or type, or to established… …   The Collaborative International Dictionary of English

  • Regular troops — Regular Reg u*lar ( l?r), a. [L. regularis, fr. regula a rule, fr. regere to guide, to rule: cf. F. r[ e]gulier. See {Rule}.] [1913 Webster] 1. Conformed to a rule; agreeable to an established rule, law, principle, or type, or to established… …   The Collaborative International Dictionary of English

  • regular — [reg′yə lər] adj. [ME reguler < MFr < L regularis, of a bar (in LL, regular) < regula: see RULE] 1. conforming in form, build, or arrangement to a rule, principle, type, standard, etc.; orderly; symmetrical [regular features] 2.… …   English World dictionary

  • Regulär — hat in verschiedenen Bereichen der Mathematik verschiedene Bedeutungen: In der abstrakten Algebra heißt ein Element einer algebraischen Struktur mit einer zweistelligen Operation regulär, wenn es kürzbar ist. Eine Halbgruppe heißt regulär, wenn… …   Deutsch Wikipedia

  • Regular Polytopes (book) — Regular Polytopes is a mathematical geometry book written by Canadian mathematician H.S.M. Coxeter. Originally written in 1947, the book was updated and republished in 1963 and 1973.The book is a comprehensive survey of the geometry of regular… …   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

Share the article and excerpts

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