Wir haben bisher von Endlichen Automaten erkannte Sprachen kennen gelernt (und diese mehr intuitiv als fundiert). In diesem Kapitel wollen wir Sprachen allgemeiner definieren und ein Beschreibungsmittel für Sprachen einführen, das es erlaubt, schrittweise alle Worte einer Sprache zu erzeugen. Solche mittels regulärer Ausdrücke beschreibbaren Sprachen sind genau die, die von Endlichen Automaten erkannt werden können. Wir werden jedoch auch zeigen, dass es formale Sprachen gibt, die nicht von Endlichen Automaten erkannt werden können.
Wir können uns leicht überlegen, dass jede endliche Menge von Zeichenketten von einem Endlichen Automaten erkannt werden kann, denn wir brauchen nur einen Automaten zu entwerfen, der für jede dieser endlich vielen Zeichenketten einen Endzustand besitzt, in den der Automat auf genau eine Weise gelangen kann. Wir wollen uns nun fragen, wieso ein Automat, der nur endlich viele Zustände besitzt, in der Lage sein kann, unendlich viele korrekt gebildete Zeichenketten von unendlich vielen falsch gebildeten zu unterscheiden. Das ist nur dann möglich, wenn die Zeichenketten nach strengen Regeln aufgebaut sind, die es erlauben, sie durch einmaliges Lesen von links nach rechts zu analysieren, ohne jemals zurückschauen zu müssen.
Diese Regeln werden in Form von regulären Ausdrücken beschrieben.
Definition: regulärer Ausdruck / Sprache
Es sei X ein Alphabet, also eine endliche Menge von Zeichen, und X* die Menge aller Worte über diesem Alphabet, also die Menge aller endlichen Folgen von Zeichen aus X einschließlich des leeren Wortes \in. Wir nennen dann jede Teilmenge L \subset X^{*} eine Sprache über dem Alphabet X. Wenn A ein endlicher Akzeptor ist, so bezeichnen wir die von ihm erkannte Sprache mit L(A).
Für Sprachen über demselben Alphabet können wir gewisse Verknüpfungen definieren. Es seien {L, L_1 \text{und} \ L_2 \subseteq X^{*}}.
Die Konkatenation (das Produkt oder Aneinanderreihung) von L_1 und L_2, bezeichnet mit L_1 \circ L_2 (oder kurz L_1 L_2), ist die Menge aller Worte aus X*, für die eine Zerlegung in einen Wortanfang aus L_1 und ein Wortende aus L_2 möglich ist: {L_1 L_2 := \{ xy \ \vert \ x \in L_1, y \in L_2 \}}
Die i-te Potenz von L für i \in \mathbb{N}_0, bezeichnet mit Li, ist die Menge aller Worte aus X*, die aus i beliebigen Worten von L aneinandergereiht sind: {L^{0} := \{ \varepsilon \}, L^{1} := L, L^{i+1} := L^{i}L}
Die Iteration von L, bezeichnet mit L*, ist die Menge aller Worte aus X*, die durch endlich häufiges Aneinanderreihen von Worten aus L entsteht: {L^{*} := \bigcup \limits_{i=0}^{\infty} {L^i}}
Für L = X ist also L^{*} die Menge aller Worte über dem Alphabet X in Übereinstimmung mit der früheren Bezeichnung X*.
Beispiel 1
Es seien {X = \{a, b\}, L_1 = \{a, ab\}, L_2 = \{b, ba\}}. Dann ist
{L_1 \circ L_2 = L_1 L_2 = \{ab, aba, abb, abba \}}
Hinweis: Die Konkatenation ist nicht kommutativ, d. h. ba oder auch bba gehören nicht zu L_1 L_2.
Beispiel 2
Es seien {X = \{a, b\}, L_1 = \{ab, a\}, L_2 = \{\varepsilon, a, aab, abb\}, L = \{a, bb\}}. Dann ist
{\begin{aligned} L_1 L_2 &= \{ab, aba, abaab, ababb, b, ba, baab, babb\} \\ &= \{b, ab, ba, aba, baab, babb, abaab, ababb\} \end{aligned} } {\begin{aligned} L^{*} &= \{\varepsilon, a, bb, aa, bba, abb, bbbb, aaa, bbaa, abba, bbbba, aabb, bbabbb, abbbb, bbbbbb, ...\} \\ &= \{\varepsilon, a, aa, bb, aaa, abb, bba, aaaa, aabb, ...\} \end{aligned}}Die endliche Menge L_1 L_2 ist durch die Aufzählung ihrer Elemente einfach zu beschreiben. Die unendliche Menge L* kann besser verbal beschrieben werden als die Menge aller Worte aus X*, bei denen die b paarweise auftreten, einschließlich des leeren Worts.
Wir führen deshalb ein neues Beschreibungsmittel für Wortmengen über einem Alphabet ein. Es wird uns erlauben, auch die Menge L* in einer einprägsamen Schreibweise anzugeben => reguläre Ausdrücke
