Eine reguläre Sprache ist eine formale Sprache, die einer Reihe von relativ strengen Einschränkungen unterliegt. Ob eine Sprache mehr oder weniger eingeschränkt ist, ergibt sich aus ihrer Stellung innerhalb der Chomsky-Hierarchie. Meint man die Menge aller regulären Sprachen, so spricht man auch von der Klasse der regulären Sprachen. Die Klasse der regulären Sprachen gehört innerhalb der Chomsky-Hierarchie den am meisten eingeschränkten Sprachklassen vom sogenannten Typ 3 an. Sie bilden damit eine echte Teilmenge der kontextfreien Sprachen, die weniger eingeschränkt sind. Dennoch handelt es sich um eine sehr natürliche Sprachklasse, die in der Linguistik, der Informatik, sowie auch bei der Konstruktion mechanischer Geräte eine hohe praktische Bedeutung erlangt hat.

Im Unterschied zu einer natürlichen Sprache bezeichnet man im Rahmen der Theorie der formalen Sprachen beliebige Symbolfolgen als Wort. Die Menge der für ein Wort erlaubten Symbole heißt Alphabet. Eine Menge von Wörtern, die aus solchen erlaubten Symbolen bestehen, nennt man eine formale Sprache. Eine Sprache $L$ über einem Alphabet $\backslash Sigma$, das heißt eine Menge von Wörtern $L\backslash subseteq\; \backslash Sigma^\{*\}$, heißt dann regulär, wenn sie eine der folgenden äquivalenten Bedingungen erfüllt:

• $L$ wird von einer regulären Grammatik erzeugt. Die regulären Grammatiken sind gerade die rechtslinearen und linkslinearen Grammatiken.
• $L$ wird von einem endlichen Automaten akzeptiert.
• $L$ kann durch einen regulären Ausdruck dargestellt werden.
• Die auf $\backslash Sigma^\{*\}$ durch $(x,y)\backslash in\; R\_L\; :\backslash Leftrightarrow\; (\backslash forall\; z\backslash in\; \backslash Sigma^\{*\}:(xz\backslash in\; L\backslash Leftrightarrow\; yz\backslash in\; L))$ definierte Relation $R\_L$ hat endlichen Index (Satz von Myhill-Nerode).

Will man für eine gegebene Sprache nachweisen, dass sie regulär ist, so muss man sie demnach auf eine reguläre Grammatik, einen endlichen Automaten oder einen regulären Ausdruck oder auf bereits bekannte reguläre Sprachen zurückführen. Für einen Nachweis, dass eine Sprache $L$ nicht regulär ist, ist es meistens zweckmäßig, das Pumping-Lemma für reguläre Sprachen zu benutzen oder in schwierigeren Fällen nachzuweisen, dass der Index von $R\_L$ nicht endlich ist.

Beispiele

---

Sei $\backslash Sigma$ ein Alphabet.

• Alle endlichen Sprachen $L\backslash subseteq\; \backslash Sigma^\{*\}$, $\backslash left|\; L\; \backslash right|\backslash in\backslash mathbb\{N\}$ sind regulär.
• Alle kontextfreien Sprachen über einem unregulären Alphabet, d.h. $\backslash left|\backslash Sigma\backslash right|=1$, sind regulär.

Abschlusseigenschaften

---

Die Klasse der regulären Sprachen ist abgeschlossen unter den gewöhnlichen Mengenoperationen Vereinigung, Durchschnitt und Komplement. Darüber hinaus gilt die Abgeschlossenheit auch für die Konkatenation und den sogenannten Kleene-Stern. Im einzelnen gilt also:

• Die Vereinigung $L\; =\; L\_1\; \backslash cup\; L\_2$ zweier regulärer Sprachen $L\_1$ und $L\_2$ ist regulär.
• Der Durchschnitt $L\; =\; L\_1\backslash cap\; L\_2$ zweier regulärer Sprachen $L\_1$ und $L\_2$ ist regulär.
• Das Komplement $\backslash complement\; L$ einer regulären Sprache $L$ ist regulär.
• Die Konkatenation $\backslash \{uv\; \backslash mid\; u\backslash in\; L\_1\; \backslash and\; v\backslash in\; L\_2\backslash \}$ zweier regulärer Sprachen $L\_1$ und $L\_2$ ist regulär.
• Der Kleene-Stern $L^\{*\}$ einer regulären Sprache $L$, d.h. die beliebig häufige Konkatenation von Wörtern aus der Sprache $L$ vereinigt mit dem leeren Wort, ist regulär.

Typische Entscheidungsprobleme

---

Seien $L$, $L\_1$ und $L\_2$ gegebene reguläre Sprachen über dem Alphabet $\backslash Sigma$. Dann ergeben sich folgende typische Problemstellungen:

• Wortproblem: Gehört ein Wort $w\backslash in\backslash Sigma^\{*\}$ zu $L$?
• Leerheitsproblem: Ist $L$ die leere Menge?
• Endlichkeitsproblem: Besteht $L$ aus einer endlichen Menge von Wörtern?
• Äquivalenzproblem: Gilt $L\_1=L\_2$?

Alle diese Probleme sind entscheidbar. Sie gelten — mit einer Ausnahme — auch noch für die analog formulierten Probleme über den kontextfreien Sprachen. Die Ausnahme ist das Äquivalenzproblem, das bereits ab den kontextfreien Sprachen (also der nach der Chomsky-Hierarchie nächst höheren Sprachklasse) nicht mehr entscheidbar ist.

Literatur

---

• Michael Sipser: Introduction to the Theory of Computation, PWS Publishing (1997) - Chapter 1, Regular Languages

Compilerbau | Linguistik | Formale Sprachen | Automatentheorie

Regulární jazyk | Regular language | Lenguaje regular | Säännöllinen kieli | שפה רגולרית | Linguaggio regolare | 正規言語 | Język regularny | Limbaje regulate | 正则语言