Konkatenation regulärer Sprachen

Seien L₁, L₂ zwei reguläre Sprachen. Wir beweisen, dass ihre Verkettung bzw. Konkatenation L = L₁ ∘ L₂ ebenfalls eine reguläre Sprache ist.

Was ist Konkatenation

Durch die Verkettung der beiden Wörter „010“ und „1111“ entsteht das Wort „0101111“. Durch die Verkettung von Sprachen entsteht eine neue Sprache, die wir konstruieren, indem wir jedes Wort der einen Sprache mit jedem Wort der anderen Sprache verketten. Die Konkatenation zweier Wörter und zweier Sprachen bezeichnen wir mit einem Kringel: ∘. Die Verkettung der Sprachen L₁ und L₂ können wir dann so definieren:

$$L_1\circ L_2=\{a\circ b|a\in L_1,b\in L_2\}$$

Beweisidee

Wir haben zwei reguläre Sprachen L₁, L₂ und zwei Automaten, die diese Sprachen akzeptieren:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Wir konstruieren einen nichtdeterministischen Automaten A = ⟨Q, Σ, δ, q, F⟩, der beide Automaten A₁ und A₂ „in sich enthält“. Die Grundidee ist, dass wir das Wort zunächst mit dem Automaten A₁ akzeptieren, und wenn der Automat A₁ einen Endzustand erreicht, versuchen wir, den Rest des Wortes noch mit dem Automaten A₂ zu akzeptieren. Wenn auch dieser Automat den Rest des Wortes akzeptiert, dann akzeptiert der Automat A das Wort.

Beispiel

Gegeben sei dieser Automat A₁, der nichtleere Wörter akzeptiert, die nur aus Nullen bestehen, sowie Wörter, die aus einer Eins bestehen, auf die nur Nullen folgen (1, 10, 100, …):

Außerdem sei dieser Automat A₂ gegeben, der Wörter akzeptiert, die auf 01 enden:

Wir verbinden die Automaten, indem wir von allen Endzuständen des Automaten A₁ ε-Übergänge in den Startzustand des Automaten A₂ hinzufügen und die Endzustände von A₁ anschließend zu gewöhnlichen Zuständen machen. Der Startzustand des gesamten neuen Automaten ist der Startzustand des Automaten A₁:

Wie funktioniert der Automat? Wir beginnen mit der Simulation des Automaten A₁. Wenn wir in einen ehemaligen Endzustand q₁ oder q₂ gelangen, wissen wir, dass der Automat A₁ einen Teil dieses Wortes akzeptiert. Damit das ganze Wort zur Sprache L₁ ∘ L₂ gehört, muss der Rest des Wortes noch vom zweiten Automaten A₂ akzeptiert werden – deshalb führen von allen ehemaligen Endzuständen ε-Übergänge in den ursprünglichen Startzustand des Automaten A₂.

Nehmen wir als Beispiel das Wort 0001. Es gehört zur Konkatenation beider Sprachen, weil das Wort durch die Verkettung der Wörter 00 ∘ 01 entstehen kann. Genauso kann es aber auch durch die Verkettung der Wörter 0 ∘ 001 entstehen. In unserem Automaten können wir beide Wege simulieren. Der Automat kann diesen Weg nehmen:

$$q_0{\to }^0{q}_1{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

Auf diesem Weg würde der Automat zuerst den Teil 00 des Wortes „akzeptieren“ und dann den Teil 01. Oder er kann diesen Weg nehmen:

$$q_0{\to }^0{q}_1{\to }^{\epsilon }{p}_0{\to }^0{p}_0{\to }^0{p}_1{\to }^1{p}_2$$

und der Automat würde so zuerst den Teil 0 des Wortes „akzeptieren“ und dann den Teil 001. In beiden Fällen gelangen wir natürlich in den Endzustand p₂.

Formales Vorgehen

Noch einmal: Wir haben zwei reguläre Sprachen L₁, L₂ und zwei Automaten, die diese Sprachen akzeptieren:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Wir konstruieren einen nichtdeterministischen Automaten A = ⟨Q, Σ, δ, q, F⟩, für den gilt:

• Q = Q₁ ∪ Q₂ (dabei nehmen wir an, dass Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Die Übergangsfunktion δ bauen wir schrittweise auf:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{falls}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{falls}& q\in F_1\wedge a\ne \epsilon \\ {\delta }_1(q,a)\cup \left\{p_0\right\}& \text{falls}& q\in F_1\wedge a=\epsilon \\ {\delta }_2(q,a)& \text{falls}& q\in Q_2\end{array}$$

Quellen

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools