Konkatenering av reguljära språk

Låt L₁, L₂ vara två reguljära språk. Vi bevisar att deras konkatenering L = L₁ ∘ L₂ också är ett reguljärt språk.

Vad är konkatenering

När vi konkatenerar de två orden ”010” och ”1111” får vi ordet ”0101111”. Konkateneringen av två språk är ett nytt språk som vi konstruerar genom att konkatenera varje ord från det ena språket med varje ord från det andra. Konkateneringen av två ord och av två språk betecknar vi med ringoperatorn: ∘. Då kan vi definiera konkateneringen av språken L₁ och L₂ så här:

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

Idén bakom beviset

Vi har två reguljära språk L₁, L₂ och två automater som accepterar språken:

$$\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}$$

Vi konstruerar en icke-deterministisk automat A = ⟨Q, Σ, δ, q, F⟩ som ”innehåller” båda automaterna A₁ och A₂. Grundidén är att vi börjar acceptera ordet med automaten A₁, och när automaten A₁ kommer till ett sluttillstånd försöker vi acceptera resten av ordet med automaten A₂. Om också den automaten accepterar resten av ordet, så accepterar automaten A ordet.

Exempel

Låt oss ta den här automaten A₁, som accepterar icke-tomma ord som består av bara nollor och ord som består av en etta följd av bara nollor (1, 10, 100, …):

och den här automaten A₂, som accepterar ord som slutar på 01:

Vi sammanfogar automaterna genom att från alla sluttillstånd i automaten A₁ lägga till epsilonövergångar till starttillståndet i automaten A₂ och sedan göra sluttillstånden i A₁ till vanliga tillstånd. Starttillståndet i hela den nya automaten blir starttillståndet i automaten A₁:

Hur fungerar automaten? Vi börjar simulera automaten A₁. Om vi går över till det tidigare sluttillståndet q₁ eller q₂ vet vi att automaten A₁ accepterar en del av ordet. För att hela ordet ska tillhöra språket L₁ ∘ L₂ måste resten av ordet accepteras av den andra automaten A₂ – därför går det epsilonövergångar från alla tidigare sluttillstånd till det ursprungliga starttillståndet i automaten A₂.

Låt oss ta ordet 0001 som exempel. Det tillhör konkateneringen av båda språken, eftersom ordet kan bildas genom att konkatenera orden 00 ∘ 01. Men det kan lika gärna bildas genom att konkatenera orden 0 ∘ 001. I vår automat kan vi simulera båda sätten. Automaten kan gå den här vägen:

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

Längs den här vägen skulle automaten först ”acceptera” delen 00 av ordet och sedan delen 01. Eller så kan den gå den här vägen:

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

och automaten skulle då först ”acceptera” delen 0 av ordet och sedan delen 001. I båda fallen kommer vi naturligtvis fram till sluttillståndet p₂.

Formell metod

Ännu en gång: Vi har två reguljära språk L₁, L₂ och två automater som accepterar språken:

$$\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}$$

Vi konstruerar en icke-deterministisk automat A = ⟨Q, Σ, δ, q, F⟩ för vilken det gäller att:

• Q = Q₁ ∪ Q₂ (vi förutsätter också att Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Övergångsfunktionen δ bygger vi upp steg för steg:

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

Källor

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