Konkatenering av regulære språk

La oss ha to regulære språk L₁, L₂. Vi skal bevise at konkateneringen L = L₁ ∘ L₂ også er et regulært språk.

Hva konkatenering er

Ved å koble sammen ordene «010» og «1111» får vi ordet «0101111». Ved å konkatenere språk får vi et nytt språk, som vi konstruerer ved å koble hvert ord fra det ene språket sammen med hvert ord fra det andre språket. Konkatenering av to ord og av to språk betegner vi med en ring: ∘. Da kan vi definere konkateneringen av språkene L₁ og L₂ slik:

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

Ideen bak beviset

Vi har to regulære språk L₁, L₂ og to automater som aksepterer disse språkene:

$$\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 konstruerer en ikke-deterministisk automat A = ⟨Q, Σ, δ, q, F⟩ som «inneholder» begge automatene A₁ og A₂. Grunnideen er at vi begynner å akseptere ordet med automaten A₁, og når automaten A₁ kommer til en sluttilstand, prøver vi å akseptere den resterende delen av ordet med automaten A₂. Hvis også denne automaten aksepterer den delen av ordet, aksepterer automaten A ordet.

Eksempel

La oss ha denne automaten A₁, som aksepterer ikke-tomme ord som bare består av nuller, og ord som består av en ener etterfulgt av bare nuller (1, 10, 100, …):

og videre denne automaten A₂, som aksepterer ord som slutter på 01:

Vi setter automatene sammen ved å legge til epsilonoverganger fra alle sluttilstandene i automaten A₁ til starttilstanden i automaten A₂, og så gjør vi sluttilstandene i A₁ til vanlige tilstander. Starttilstanden i hele den nye automaten blir starttilstanden i automaten A₁:

Hvordan kommer automaten til å fungere? Vi begynner å simulere automaten A₁. Hvis vi går over til den tidligere sluttilstanden q₁ eller q₂, vet vi at automaten A₁ aksepterer en del av dette ordet. For at hele ordet skal være med i språket L₁ ∘ L₂, må den resterende delen av ordet aksepteres av den andre automaten A₂ — derfor går det epsilonoverganger fra alle de tidligere sluttilstandene til den opprinnelige starttilstanden i automaten A₂.

Som eksempel tar vi ordet 0001. Det tilhører konkateneringen av begge språkene, for ordet kan bli til ved å koble sammen ordene 00 ∘ 01. Men det kan like godt bli til ved å koble sammen ordene 0 ∘ 001. I automaten vår kan vi simulere begge framgangsmåtene. Automaten kan gå denne veien:

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

På denne veien ville automaten først «akseptert» delen 00 av ordet og deretter delen 01. Eller den kan gå denne veien:

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

og automaten ville da først «akseptert» delen 0 av ordet og så delen 001. I begge tilfeller kommer vi selvfølgelig til sluttilstanden p₂.

Formell framgangsmåte

Enda en gang: Vi har to regulære språk L₁, L₂ og to automater som aksepterer disse språkene:

$$\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 konstruerer en ikke-deterministisk automat A = ⟨Q, Σ, δ, q, F⟩ som oppfyller:

• Q = Q₁ ∪ Q₂ (vi antar samtidig at Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

Overgangsfunksjonen δ bygger vi opp etter hvert:

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

Kilder

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