Lexikon der Mathematik: reguläre Sprache
manchmal auch reguläre Menge genannt, Sprache, zu der es einen sie definierenden regulären Ausdruck gibt.
Jede der folgenden Bedingungen ist äquivalent zur Regularität einer Sprache L:
- Es gibt einen deterministischen endlichen Automaten, derL akzeptiert;
- es gibt einen nichtdeterministischen endlichen Automat, der L akzeptiert;
- es gibt eine linkslineare Grammatik für L;
- es gibt eine rechtslineare Grammatik für L;
- die Nerode-Äquivalenz zerlegt L in endlich viele Klassen;
- L besitzt in der Chomsky-Hierarchie den Typ 3.
Eine notwendige Bedingung für die Regularität einer Sprache liefert das Pumping-Lemma für reguläre Sprachen.
Wegen den genannten Beziehungen zu endlichen Automaten und einfachen Grammatiken werden reguläre Sprachen oft zur Definition von Bestandteilen von Programmiersprachen verwendet. Für die Definition kompletter Programmiersprachen sind sie selten verwendbar, weil diese häufig geklammerte Strukturen (Klammersprache) beinhalten, die grundsätzlich nicht regulär beschreibbar sind. Reguläre Sprachen charakterisieren wegen ihrer Beziehung zu endlichen Automaten auch das Verhalten vieler diskreter dynamischer Systeme.
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.