Reguláris nyelv lezárása

Adott egy L reguláris nyelv. Bebizonyítjuk, hogy az L nyelv lezárása is reguláris nyelv.

Mi a nyelv lezárása

Az L nyelv lezárását L^∗ jelöli. A lezárás tartalmazza mindazokat a szavakat, amelyek az L nyelv szavainak véges sok összefűzésével előállíthatók. A lezárást így definiálhatjuk:

$$L^{\ast }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in \mathbb{N}\},$$

ahol ∘ az összefűzés műveletét jelöli. A lezárás az üres szót is tartalmazza, azaz az ϵ-t.

Formális eljárás

Nagyon hasonlóan járunk el, mint a nyelvek összefűzésénél. Csak két különböző automata összekapcsolása helyett egyetlen automatát kapcsolunk össze önmagával – az automata végállapotaiból epszilon-átmeneteket vezetünk az automata kezdőállapotába. A lezárásnak azonban tartalmaznia kell az üres szót is. Hogyan érjük ezt el? A kezdőállapotot végállapottá tehetnénk. Akkor az ilyen automata elfogadná az üres szót, de elfogadhatna más szavakat is. Ezért inkább létrehozunk egy új kezdőállapotot, és ebből epszilon-átmenetet vezetünk az eredeti kezdőállapotba.

Adott egy L₁ reguláris nyelv és egy automata, amely ezt a nyelvet elfogadja:

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

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

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

A δ átmeneti függvényt így definiáljuk:

$$\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 ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{ha}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{ha}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{ha}& q=q_s\wedge a\ne ϵ\end{array}$$

Példa

Adott ez az A₁ automata, amely a 00 vagy 11 szavakat fogadja el:

Az L(A₁) nyelv lezárása így az a nyelv, amely mindazokat a szavakat tartalmazza, amelyek 00 és 11 párokból állnak, például 0000, 110011, 11110000 és így tovább. Azt az automatát, amely ezt a lezárást elfogadná, úgy szerkesztenénk meg, hogy létrehoznánk egy új q_s kezdőállapotot, amelyből epszilon-átmenet vezet az egykori q₀ kezdőállapotba, és epszilon-átmeneteket adnánk a q₃ és q₄ állapotból a q₀ állapotba:

Ellenőrizhetjük, hogy ez az automata valóban elfogadja a 0000, 110011, 11110000 szavakat, de például az 1010 szót nem fogadja el.

Források

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