Reguláris nyelvek összefűzése

Legyen adott két reguláris nyelv, L₁, L₂. Bebizonyítjuk, hogy az összefűzésük (konkatenációjuk), L = L₁ ∘ L₂ is reguláris nyelv.

Mi az a konkatenáció

A „010” és az „1111” szó összefűzésével a „0101111” szó keletkezik. Nyelvek összefűzésével új nyelv keletkezik, amelyet úgy szerkesztünk meg, hogy az egyik nyelv minden szavát összefűzzük a másik nyelv minden szavával. Két szó és két nyelv konkatenációját egy kis körrel jelöljük: ∘. Az L₁ és L₂ nyelv összefűzését ekkor így definiálhatjuk:

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

A bizonyítás ötlete

Adott két reguláris nyelv, L₁, L₂, és két automata, amely ezeket elfogadja:

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

Megszerkesztünk egy A = ⟨Q, Σ, δ, q, F⟩ nemdeterminisztikus automatát, amely „magában foglalja” az A₁ és az A₂ automatát is. Az alapötlet az, hogy a szót az A₁ automatával kezdjük elfogadni, és amikor az A₁ automata végállapotba jut, a szó hátralévő részét megpróbáljuk még elfogadtatni az A₂ automatával. Ha ez az automata is elfogadja a szó egy részét, akkor az A automata elfogadja a szót.

Példa

Adott ez az A₁ automata, amely elfogadja a csak nullákból álló nemüres szavakat, valamint azokat a szavakat, amelyek egy egyesből állnak, és utána csak nullák következnek (1, 10, 100, …):

továbbá adott ez az A₂ automata, amely azokat a szavakat fogadja el, amelyek 01-re végződnek:

Az automatákat úgy kapcsoljuk össze, hogy az A₁ automata összes végállapotából epszilon-átmenetet vezetünk az A₂ automata kezdőállapotába, majd az A₁ végállapotait közönséges állapotokká tesszük. Az egész új automata kezdőállapota az A₁ automata kezdőállapota lesz:

Hogyan fog működni az automata? Az A₁ automata működésének szimulálásával kezdünk. Ha átmegyünk a q₁ vagy q₂ egykori végállapotba, akkor tudjuk, hogy az A₁ automata elfogadja ennek a szónak egy részét. Ahhoz, hogy az egész szó az L₁ ∘ L₂ nyelvhez tartozzon, a szó hátralévő részét még el kell fogadnia a második automatának, az A₂-nek – ezért vezet az összes egykori végállapotból epszilon-átmenet az A₂ automata eredeti kezdőállapotába.

Vegyük például a 0001 szót. Ez mindkét nyelv összefűzéséhez tartozik, mert a szó keletkezhet a 00 ∘ 01 szavak összefűzésével. De ugyanígy keletkezhet a 0 ∘ 001 szavak összefűzésével is. Az automatánkban mindkét eljárást le tudjuk szimulálni. Az automata haladhat ezen az úton:

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

Ezen az úton az automata először „elfogadná” a szó 00 részét, majd a 01 részét. Vagy haladhat ezen az úton:

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

és így az automata először „elfogadná” a szó 0 részét, majd a 001 részét. Mindkét esetben természetesen a p₂ végállapotba jutunk.

Formális eljárás

Még egyszer: adott két reguláris nyelv, L₁, L₂, és két automata, amely ezeket a nyelveket elfogadja:

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

Megszerkesztjük az A = ⟨Q, Σ, δ, q, F⟩ nemdeterminisztikus automatát, amelyre teljesül:

• Q = Q₁ ∪ Q₂ (egyúttal feltesszük, hogy Q₁ ∩ Q₂ = ∅)
• Σ= Σ₁ ∪ Σ₂
• q = q₀
• F = F₂

A δ átmeneti függvényt fokozatosan állítjuk össze:

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

Források

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