Union av reguljära språk

Låt L₁, L₂ vara två reguljära språk. Vi bevisar att deras union L = L₁ ∪ L₂ också är ett reguljärt språk.

Metod med en deterministisk automat

Idén bakom metoden

Vi har två reguljära språk L₁ och L₂ och vill bevisa att deras union L₁ ∪ L₂ också är ett reguljärt språk. Eftersom L₁ och L₂ är reguljära språk finns det ändliga automater A₁ och A₂ som accepterar språken L₁ och L₂, alltså gäller L(A₁) = L₁ och L(A₂) = L₂. Vi konstruerar sedan en ändlig automat A som accepterar språket L₁ ∪ L₂, och därmed har vi bevisat att språket L₁ ∪ L₂ är reguljärt.

Hur gör vi det? Vi har de ändliga automaterna A₁ och A₂, som accepterar vart och ett av språken. Vi kan säga att ordet w tillhör språket L₁ ∪ L₂ om och endast om minst en av automaterna A₁ och A₂ accepterar det.

Automaten A skulle kunna fungera så att den för indata w simulerar automaten A₁:s beräkning för indata w. Om A₁ accepterar ordet w, accepterar också A ordet w. Om A₁ förkastar ordet w, försöker A i stället simulera A₂:s beräkning för indata w. Om A₂ accepterar ordet w, accepterar också A ordet w. I annat fall förkastas ordet.

Nu återstår att formalisera vad det betyder att automaten A ”simulerar” en annan automats beräkning.

Formalisering

Vi har två reguljära språk L₁ och L₂ som accepteras av de ändliga automaterna

$$\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 konstruerar en ändlig automat A = ⟨Q, Σ, δ, q, F⟩ som accepterar språket L = L₁ ∪ L₂. Vi använder idén att simulera de två automaterna A₁, A₂. Tänk dig att vi har ordet w = w₁w₂… w_n som indata och att vi samtidigt simulerar hur automaterna A₁ och A₂ arbetar med ordet w. Startkonfigurationen för automaten A₁ är ⟨q₁, w₁w₂… w_n⟩ och startkonfigurationen för A₂ är ⟨q₂, w₁w₂… w_n⟩. I varje automat utför vi nu ett beräkningssteg, och då hamnar vi i konfigurationerna ⟨δ₁(q₁, w₁), w₂… w_n⟩ och ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vi ser att konfigurationerna skiljer sig bara i den första komponenten. Den andra komponenten, den del av ordet som ännu inte har lästs, är alltid densamma. Under simuleringen behöver vi alltså inte hålla reda på två konfigurationer för två automater, utan en konfiguration av formen ⟨⟨q_i, q_j⟩, w_l… w_n⟩ räcker, där q_i ∈ Q₁ och q_j ∈ Q₂. Med andra ord har automaten A som vi konstruerar startkonfigurationen ⟨⟨q₁, q₂⟩, w⟩. Den första delen av paret ⟨q₁, q₂⟩ är det tillstånd som automaten A₁ befinner sig i just nu, och den andra komponenten är det aktuella tillståndet i automaten A₂.

Vi kan alltså skriva att automaten A har tillståndsmängden Q = Q₁ × Q₂. Det är den kartesiska produkten av tillstånden i de två tidigare automaterna. Nästa idé är att automaten A har starttillståndet ⟨q₁, q₂⟩, och om automaten A₁ för symbolen w₁ går över till tillståndet q_i och automaten A₂ för symbolen w₁ går över till tillståndet q_j, så går automaten A för symbolen w₁ över till tillståndet ⟨q_i, q_j⟩.

Vi skriver övergångsfunktionen δ så här (här förutsätter vi redan att vi befinner oss i tillstånden q_i och q_j):

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

Nu återstår bara några detaljer. För alfabetet gäller Σ= Σ₁ ∪ Σ₂. Starttillståndet är q = ⟨q₁, q₂⟩. Sluttillstånden är alla par ⟨q_i, q_j⟩ sådana att antingen q_i ∈ F₁ eller q_j ∈ F₂.

Illustration av metoden

Låt oss ta två automater. Den första är automaten A₁, som accepterar alla ord (inklusive det tomma ordet) där nollor och ettor alternerar, dvs. ord av formen 01, 0101, 010101, …

Den andra automaten A₂ accepterar ord som innehåller minst en nolla:

Unionen av dessa språk består av de ord som antingen innehåller en nolla eller har formen 01, 0101, … Nu konstruerar vi en ändlig automat A = ⟨Q, Σ, δ, q, F⟩ som accepterar just detta unionsspråk. Först visar vi hur tillstånden i den nya automaten A ser ut. Det blir den kartesiska produkten av tillstånden i den första och den andra 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⟩\}$$

Så här ser de sex tillstånden ut i automaten A, som accepterar unionsspråket L(A₁) ∪ L(A₂). I tillståndsdiagrammet skulle de se ut så här:

Bli inte förvirrad av att tillstånden består av par av tillstånd. Det är bara till för att ge bättre överblick över vad som händer i automaten. Tillstånden skulle lika gärna kunna heta q₀, …, q₅ som vanligt. Sluttillstånden är de tillstånd som innehåller antingen q₀ eller p₁, som är sluttillstånd i de ursprungliga automaterna. Starttillståndet är ⟨q₀, p₀⟩.

Nu måste vi hitta alla övergångar. Vi skriver upp en sådan 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}$$

Sedan fyller vi i tabellen steg för steg. Först tar vi reda på vart övergången från tillståndet ⟨q₀, p₀⟩ leder för indata 0. Vi tittar på vart övergången från tillståndet q₀ för indata 0 leder i automaten A₁: den leder till tillståndet q₁. I automaten A₂ leder övergången från p₀ för nollan till tillståndet p₁. Därför skriver vi in ⟨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}$$

För indata 1 får vi: för automaten A₁ har vi δ₁(q₀, 1) = q₂ och för automaten A₂ har vi δ₂(p₀, 1) = p₀. Vi får alltså tillståndet ⟨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 fyller i 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}$$

Utifrån den här tabellen ritar vi sedan resten av diagrammet.

Vi kan pröva om automaten fungerar som den ska. Vi försöker låta den acceptera ordet 0100. Automaten går efter tur genom tillstånden

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

Eftersom tillståndet ⟨q₂, p₁⟩ är ett sluttillstånd accepterar automaten A ordet 0100. Hur skulle det gå om vi försökte låta automaterna A₁ och A₂ acceptera ordet 0100? Automaten A₁ skulle gå genom följande tillstånd:

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

Automaten slutade i tillståndet q₂, som inte är ett sluttillstånd, så automaten A₁ skulle inte acceptera ordet. Hur går det för automaten A₂?

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

Tillståndet p₁ är ett sluttillstånd, så automaten A₂ skulle acceptera ordet 0100. Lägg märke till att automaterna A₁ och A₂ slutade i tillstånden q₂ och p₁, vilket stämmer med att automaten A slutade i tillståndet ⟨q₂, p₁⟩.

Metod med en icke-deterministisk automat

Exempel

Att mängden av reguljära språk är sluten under union kan vi också bevisa genom att konstruera en icke-deterministisk automat, som blir mycket enklare.

Vi har alltså två reguljära språk L₁, L₂ och vill bevisa att deras union L = L₁ ∪ L₂ också är ett reguljärt språk. Eftersom L₁, L₂ är reguljära språk måste det finnas automater A₁, A₂ som accepterar dessa språk. Det vill säga L(A₁) = L₁ och L(A₂) = L₂. Med hjälp av de här automaterna konstruerar vi en automat A som accepterar språket L, dvs. L(A) = L.

Anta att de ändliga automaterna A₁ och A₂ ser ut så här:

och

En automat som accepterar unionen av de båda språken konstruerar vi genom att skapa ett nytt starttillstånd och från det tillståndet dra två epsilonövergångar till de ursprungliga starttillstånden. Det är allt. Automaten skulle se ut så här:

Formalisering

Vi har två automater A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ och A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Vi konstruerar en automat A = ⟨Q, Σ, δ, q₀, F⟩ som accepterar unionen av de språk som accepteras av de föregående automaterna, dvs. L(A) = L(A₁) ∪ L(A₂). Här gäller:

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

Övergångsfunktionen δ definierar vi så här:

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

Källor

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