Union av regulære språk

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

Framgangsmåte med deterministisk automat

Ideen bak framgangsmåten

Vi har to regulære språk L₁ og L₂, og vi vil bevise at unionen L₁ ∪ L₂ igjen er et regulært språk. Siden L₁ og L₂ er regulære språk, finnes det endelige automater A₁ og A₂ som aksepterer språkene L₁ og L₂, altså gjelder L(A₁) = L₁ og L(A₂) = L₂. Vi konstruerer så en endelig automat A som aksepterer språket L₁ ∪ L₂, og dermed beviser vi at språket L₁ ∪ L₂ er regulært.

Hvordan gjør vi det? Vi har de endelige automatene A₁ og A₂ som aksepterer hvert sitt språk. Vi kan si at ordet w tilhører språket L₁ ∪ L₂ hvis og bare hvis minst én av automatene A₁ eller A₂ aksepterer det.

Automaten A kunne fungere slik at den for input w simulerer beregningen til automaten A₁ for input w. Hvis A₁ aksepterer ordet w, aksepterer også A ordet w. Hvis A₁ avviser ordet w, prøver A i tillegg å simulere beregningen til A₂ for input w. Hvis A₂ aksepterer ordet w, aksepterer også A ordet w. I motsatt fall avviser den.

Vi må da formalisere hva det betyr at automaten A «simulerer» beregningen til en annen automat.

Formalisering

Vi har to regulære språk L₁ og L₂ som aksepteres av de endelige automatene

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

Vi konstruerer en endelig automat A = ⟨Q, Σ, δ, q, F⟩ som aksepterer språket L = L₁ ∪ L₂. Vi bruker ideen om å simulere to automater A₁, A₂. La oss tenke oss at vi har ordet w = w₁w₂… w_n som input, og at vi nå samtidig simulerer forløpet til automatene A₁ og A₂ for ordet w. Startkonfigurasjonen til automaten A₁ er ⟨q₁, w₁w₂… w_n⟩, og startkonfigurasjonen til A₂ er ⟨q₂, w₁w₂… w_n⟩. I hver automat utfører vi nå et beregningssteg, og da kommer vi til konfigurasjonene ⟨δ₁(q₁, w₁), w₂… w_n⟩ og ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vi ser at disse konfigurasjonene bare er forskjellige i den første komponenten, den andre — den delen av ordet som ikke er lest — er alltid den samme. Under simuleringen trenger vi derfor ikke å holde styr på to konfigurasjoner for to automater, men det er nok med én konfigurasjon på formen ⟨⟨q_i, q_j⟩, w_l… w_n⟩, der q_i ∈ Q₁ og q_j ∈ Q₂. Med andre ord får automaten A vi konstruerer, startkonfigurasjonen ⟨⟨q₁, q₂⟩, w⟩. Den første delen av paret ⟨q₁, q₂⟩ er tilstanden som automaten A₁ befinner seg i akkurat nå, og den andre komponenten er den nåværende tilstanden til automaten A₂.

Vi kan altså skrive at automaten A vi konstruerer, får mengden av tilstander Q = Q₁ × Q₂. Det blir det kartesiske produktet av tilstandene fra de to forrige automatene. Den neste ideen er at automaten A får starttilstanden ⟨q₁, q₂⟩, og hvis automaten A₁ for symbolet w₁ går over til tilstanden q_i og automaten A₂ for symbolet w₁ går over til tilstanden q_j, går automaten A for symbolet w₁ over til tilstanden ⟨q_i, q_j⟩.

Overgangsfunksjonen δ skriver vi slik (her antar vi allerede at vi akkurat nå er i tilstandene q_i og q_j):

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

Nå gjenstår bare små detaljer. For alfabetet gjelder Σ= Σ₁ ∪ Σ₂. Starttilstanden er q = ⟨q₁, q₂⟩. Og sluttilstandene er alle par ⟨q_i, q_j⟩ slik at enten q_i ∈ F₁ eller q_j ∈ F₂.

Illustrasjon av framgangsmåten

La oss ha to automater. Den første er automaten A₁, som aksepterer alle ord (inkludert det tomme ordet) der nuller og enere veksler, altså ord på formen 01, 0101, 010101, …

Den neste automaten A₂ aksepterer ord som inneholder minst én null:

Unionen av disse språkene er ord som enten inneholder en null eller har formen 01, 0101, … Nå konstruerer vi den endelige automaten A = ⟨Q, Σ, δ, q, F⟩ som aksepterer akkurat dette språket. Først viser vi hvordan tilstandene i denne nye automaten A kommer til å se ut. Det blir det kartesiske produktet av tilstandene i den første og den andre automaten:

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

Dette er de seks tilstandene i automaten A, som aksepterer unionen L(A₁) ∪ L(A₂). I diagrammet ville de sett slik ut:

Ikke la deg skremme av at vi har tilstander som består av par av tilstander — det er bare for å gi bedre oversikt over hva som egentlig skjer i automaten. Tilstandene kunne gjerne hett q₀, …, q₅ som vanlig. Sluttilstandene er de tilstandene som inneholder enten tilstanden q₀ eller p₁, som er sluttilstandene i de opprinnelige automatene. Starttilstanden er ⟨q₀, p₀⟩.

Nå må vi finne alle overgangene. Vi skriver opp en slik tabell:

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

Og vi fyller ut tabellen etter hvert. Først finner vi ut hvor overgangen fra tilstanden ⟨q₀, p₀⟩ går ved input 0. Vi finner ut hvor overgangen fra tilstanden q₀ går ved input 0 i automaten A₁: den går til tilstanden q₁. I automaten A₂ går overgangen fra p₀ ved null til tilstanden p₁. Så vi skriver ⟨q₁, p₁⟩ i tabellen:

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

Ved input 1 får vi: for automaten A₁ har vi δ₁(q₀, 1) = q₂, og for automaten A₂ har vi δ₂(p₀, 1) = p₀. Vi får altså tilstanden ⟨q₂, p₀⟩.

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

Vi skriver inn resten av tabellen:

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

Og etter denne tabellen tegner vi bare resten av diagrammet.

Vi kan teste at automaten fungerer som den skal. Vi prøver å akseptere ordet 0100. Automaten går etter hvert gjennom tilstandene

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

Siden tilstanden ⟨q₂, p₁⟩ er en sluttilstand, aksepterer automaten A ordet 0100. Hvordan ville det gått hvis vi hadde prøvd å akseptere ordet 0100 med automatene A₁ og A₂? Automaten A₁ ville etter hvert gått gjennom disse tilstandene:

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

Automaten endte i tilstanden q₂, som ikke er en sluttilstand, så automaten A₁ ville ikke akseptert dette ordet. Hva med automaten A₂?

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

Tilstanden p₁ er en sluttilstand, så automaten A₂ ville akseptert ordet 0100. Legg merke til at automatene A₁ og A₂ endte i tilstandene q₂ og p₁, og det stemmer med at automaten A endte i tilstanden ⟨q₂, p₁⟩.

Framgangsmåte med ikke-deterministisk automat

Eksempel

At mengden av regulære språk er lukket under union, kan vi også bevise ved å konstruere en ikke-deterministisk automat, som blir mye enklere.

Vi har altså to regulære språk L₁, L₂, og vi vil bevise at unionen L = L₁ ∪ L₂ også er et regulært språk. Siden L₁, L₂ er regulære språk, må det finnes automater A₁, A₂ som aksepterer disse språkene. Altså gjelder L(A₁) = L₁ og L(A₂) = L₂. Ved hjelp av disse automatene konstruerer vi automaten A, som skal akseptere språket L, altså L(A) = L.

Anta at de endelige automatene A₁ og A₂ ser slik ut:

og

Automaten som aksepterer unionen av begge språkene, konstruerer vi ved å lage en ny starttilstand og la to epsilonoverganger gå fra denne tilstanden til de opprinnelige starttilstandene. Det er alt. Automaten ville sett slik ut:

Formalisering

Vi har to automater A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ og A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Vi konstruerer automaten A = ⟨Q, Σ, δ, q₀, F⟩ som skal akseptere unionen av språkene som de forrige automatene aksepterer, altså L(A) = L(A₁) ∪ L(A₂). Da gjelder:

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

Og overgangsfunksjonen δ definerer vi slik:

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

Kilder

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