Reguláris nyelvek uniója

Legyen adott két reguláris nyelv, L₁, L₂. Bebizonyítjuk, hogy az unió, L = L₁ ∪ L₂ is reguláris nyelv.

Eljárás determinisztikus automatával

Az eljárás ötlete

Adott két reguláris nyelv, L₁ és L₂, és be akarjuk bizonyítani, hogy az L₁ ∪ L₂ unió is reguláris nyelv. Mivel L₁ és L₂ reguláris nyelvek, léteznek olyan A₁ és A₂ véges automaták, amelyek elfogadják az L₁, illetve az L₂ nyelvet, vagyis L(A₁) = L₁ és L(A₂) = L₂. Ezután megszerkesztünk egy olyan A véges automatát, amely az L₁ ∪ L₂ nyelvet fogadja el, és ezzel bebizonyítjuk, hogy az L₁ ∪ L₂ nyelv reguláris.

Hogyan csináljuk? Kéznél van az A₁ és A₂ véges automata, amelyek külön-külön elfogadják a két nyelvet. Mondhatjuk, hogy a w szó pontosan akkor tartozik az L₁ ∪ L₂ nyelvbe, ha az A₁ és A₂ automaták közül legalább az egyik elfogadja.

Az A automata úgy működhetne, hogy a w bemenetre szimulálja az A₁ automata működését a w bemeneten. Ha A₁ elfogadja a w szót, akkor A is elfogadja a w szót. Ha A₁ elutasítja a w szót, akkor A még megpróbálja szimulálni az A₂ működését a w bemeneten. Ha A₂ elfogadja a w szót, akkor A is elfogadja a w szót. Ellenkező esetben elutasítja.

Már csak azt kell pontosan megfogalmaznunk, mit jelent az, hogy az A automata „szimulálja” egy másik automata működését.

Formalizálás

Adott két reguláris nyelv, L₁ és L₂, amelyeket az alábbi véges automaták fogadnak el:

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

Megszerkesztjük az A = ⟨Q, Σ, δ, q, F⟩ véges automatát, amely az L = L₁ ∪ L₂ nyelvet fogadja el. Kihasználjuk az ötletet, hogy egyszerre szimuláljuk az A₁, A₂ automatákat. Képzeljük el, hogy a bemeneten a w = w₁w₂… w_n szó van, és most egyszerre szimuláljuk az A₁ és A₂ működését a w szóra. Az A₁ automata kezdőkonfigurációja ⟨q₁, w₁w₂… w_n⟩, az A₂ kezdőkonfigurációja ⟨q₂, w₁w₂… w_n⟩. Mindkét automatában most végrehajtunk egy lépést, és így a ⟨δ₁(q₁, w₁), w₂… w_n⟩ és a ⟨δ₂(q₂, w₁), w₂… w_n⟩ konfigurációba jutunk.

Látjuk, hogy ezek a konfigurációk csak az első komponensben különböznek, a másodikban – a szó még el nem olvasott részében – mindig megegyeznek. A szimuláció során ezért nem kell két automata két konfigurációját nyilvántartanunk, elég egyetlen konfiguráció ⟨⟨q_i, q_j⟩, w_l… w_n⟩ alakban, ahol q_i ∈ Q₁ és q_j ∈ Q₂. Más szóval a megszerkesztendő A automata kezdőkonfigurációja ⟨⟨q₁, q₂⟩, w⟩ lesz. A ⟨q₁, q₂⟩ pár első tagja azt az állapotot jelöli, amelyben éppen az A₁ automata van, a második tag pedig az A₂ automata aktuális állapota.

Felírhatjuk tehát, hogy az A automata állapothalmaza Q = Q₁ × Q₂ lesz. Ez a két korábbi automata állapotainak Descartes-szorzata. Az ötlet a következő: az A automata kezdőállapota ⟨q₁, q₂⟩, és ha az A₁ automata a w₁ szimbólumra a q_i állapotba megy át, az A₂ automata pedig a w₁ szimbólumra a q_j állapotba, akkor az A automata a w₁ szimbólumra a ⟨q_i, q_j⟩ állapotba megy át.

A δ átmeneti függvényt így írjuk fel (itt már feltesszük, hogy éppen a q_i és q_j állapotban vagyunk):

$$\delta (⟨q_i,q_j⟩,w)=⟨{\delta }_1(q_i,w),{\delta }_2(q_j,w)⟩$$

Már csak az apróságok maradtak. Az ábécére Σ= Σ₁ ∪ Σ₂ teljesül. A kezdőállapot q = ⟨q₁, q₂⟩. A végállapotok pedig mindazok a ⟨q_i, q_j⟩ párok, amelyekre q_i ∈ F₁ vagy q_j ∈ F₂.

Az eljárás szemléltetése

Adott két automata. Az első az A₁ automata, amely elfogadja az összes olyan szót (az üres szót is), amelyben felváltva követik egymást a nullák és az egyesek, vagyis a 01, 0101, 010101, … alakú szavakat.

A másik, az A₂ automata azokat a szavakat fogadja el, amelyek tartalmaznak legalább egy nullát:

E két nyelv uniója azokból a szavakból áll, amelyek vagy tartalmaznak nullát, vagy 01, 0101, … alakúak. Most megszerkesztjük az A = ⟨Q, Σ, δ, q, F⟩ véges automatát, amely pontosan ezt az egyesített nyelvet fogadja el. Először megmutatjuk, hogyan néznek ki az új A automata állapotai. Ez az első és a második automata állapotainak Descartes-szorzata lesz:

$$Q=Q_1\times Q_2=\{⟨q_0,p_0⟩,⟨q_0,p_1⟩,⟨q_1,p_0⟩,⟨q_1,p_1⟩,⟨q_2,p_0⟩,⟨q_2,p_1⟩\}$$

Ez az A automata hat állapota, amely az L(A₁) ∪ L(A₂) egyesített nyelvet fogadja el. Az ábrán így néznének ki:

Ne ijedj meg attól, hogy az állapotok állapotpárokból állnak – ez csak azt segíti, hogy jobban átlássuk, mi történik az automatában. Az állapotokat akár egyszerűen q₀, …, q₅-nek is nevezhetnénk. A végállapotok azok az állapotok, amelyek a q₀ vagy a p₁ állapotot tartalmazzák, mert ezek az eredeti automaták végállapotai. A kezdőállapot ⟨q₀, p₀⟩.

Most meg kell találnunk az összes átmenetet. Felírunk egy ilyen táblázatot:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

A táblázatot fokozatosan töltjük ki. Először megnézzük, hová vezet átmenet a ⟨q₀, p₀⟩ állapotból a 0 bemenetre. Megnézzük, hová vezet átmenet a q₀ állapotból a 0 bemenetre az A₁ automatában: a q₁ állapotba. Az A₂ automatában a p₀ állapotból a nullára a p₁ állapotba vezet átmenet. Így a táblázatba a ⟨q₁, p₁⟩ állapotot írjuk:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

Az 1 bemenetre ezt kapjuk: az A₁ automatára δ₁(q₀, 1) = q₂, az A₂ automatára pedig δ₂(p₀, 1) = p₀. Így a ⟨q₂, p₀⟩ állapotot kapjuk.

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_0,p_1⟩\\ ⟨q_1,p_0⟩\\ ⟨q_1,p_1⟩\\ ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩\end{array}$$

Kitöltjük a táblázat többi részét:

$$\begin{array}{ccc}& 0& 1\\ ⟨q_0,p_0⟩& ⟨q_1,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_0,p_1⟩& ⟨q_1,p_1⟩& ⟨q_2,p_1⟩\\ ⟨q_1,p_0⟩& ⟨q_2,p_1⟩& ⟨q_0,p_0⟩\\ ⟨q_1,p_1⟩& ⟨q_2,p_1⟩& ⟨q_0,p_1⟩\\ ⟨q_2,p_0⟩& ⟨q_2,p_1⟩& ⟨q_2,p_0⟩\\ ⟨q_2,p_1⟩& ⟨q_2,p_1⟩& ⟨q_2,p_1⟩\end{array}$$

E táblázat alapján pedig már csak be kell rajzolnunk az ábra többi részét.

Kipróbálhatjuk, hogy az automata úgy működik-e, ahogy kell. Próbáljuk meg elfogadtatni vele a 0100 szót. Az automata sorban ezeken az állapotokon megy végig:

$$⟨q_0,p_0⟩,⟨q_1,p_1⟩,⟨q_0,p_1⟩,⟨q_1,p_1⟩,⟨q_2,p_1⟩$$

Mivel a ⟨q₂, p₁⟩ állapot végállapot, az A automata elfogadja a 0100 szót. Mi történne, ha a 0100 szót az A₁ és A₂ automatával próbálnánk elfogadtatni? Az A₁ automata sorban ezeken az állapotokon haladna végig:

$$q_0,q_1,q_0,q_1,q_2$$

Az automata a q₂ állapotban fejezte be, ami nem végállapot, tehát az A₁ automata ezt a szót nem fogadná el. És az A₂ automata?

$$p_0,p_1,p_1,p_1,p_1$$

A p₁ állapot végállapot, tehát az A₂ automata elfogadná a 0100 szót. Figyeld meg, hogy az A₁ és A₂ automata a q₂, illetve p₁ állapotban fejezte be, ami összhangban van azzal, hogy az A automata a ⟨q₂, p₁⟩ állapotban fejezte be.

Eljárás nemdeterminisztikus automatával

Példa

Azt, hogy a reguláris nyelvek halmaza zárt az unióra, bebizonyíthatjuk egy sokkal egyszerűbb nemdeterminisztikus automata megszerkesztésével is.

Adott tehát két reguláris nyelv, L₁, L₂, és be akarjuk bizonyítani, hogy az unió, L = L₁ ∪ L₂ is reguláris nyelv. Mivel L₁, L₂ reguláris nyelvek, léteznie kell olyan A₁, A₂ automatáknak, amelyek elfogadják őket. Vagyis L(A₁) = L₁ és L(A₂) = L₂. Ezekből az automatákból megszerkesztjük az A automatát, amely az L nyelvet fogadja el, azaz L(A) = L.

Tegyük fel, hogy az A₁ és A₂ véges automata így néz ki:

és

Azt az automatát, amely elfogadná a két nyelv unióját, úgy szerkesztenénk meg, hogy létrehoznánk egy új kezdőállapotot, és ebből két epszilon-átmenetet vezetnénk az eredeti kezdőállapotokba. Ez az egész. Az automata így nézne ki:

Formalizálás

Adott két automata, A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ és A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Megszerkesztjük az A = ⟨Q, Σ, δ, q₀, F⟩ automatát, amely az előző automaták által elfogadott nyelvek unióját fogadja el, azaz L(A) = L(A₁) ∪ L(A₂). A következők teljesülnek:

• Q = Q₁ ∪ Q₂ ∪ {q₀}
• F = F₁ ∪ F₂

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

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{ha}& q\in Q_1\\ {\delta }_2(q,a)& \text{ha}& q\in Q_2\\ \{q_1,q_2\}& \text{ha}& q=q_0\wedge a=\epsilon \\ \mathrm{\varnothing }& \text{ha}& q=q_0\wedge a\ne \epsilon \end{array}$$

Források

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