Snitt av reguljära språk

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

Idén bakom beviset

Vi har två reguljära språk L₁ och L₂ och vill bevisa att deras snitt 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.

Ett ord tillhör snittet av språken om det tillhör både språket L₁ och språket L₂. Ordet måste alltså accepteras av automaten A₁ och samtidigt av automaten A₂. Vi använder precis samma idé som vid union av reguljära språk, men ändrar bara mängden av sluttillstånd.

Formalisering av metoden

Vi har två automater,

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

Vi konstruerar en automat A = ⟨Q, Σ, δ, q, F⟩ som accepterar språket L(A₁) ∩ L(A₂). Det gäller att

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

För övergångsfunktionen δ gäller följande samband:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Exempel

Låt oss ta den här automaten A₁, som accepterar alla ord som innehåller ett jämnt antal ettor:

och automaten A₂, som accepterar ord som innehåller ett udda antal nollor:

Vi konstruerar en automat som accepterar snittet av dessa språk. Tillståndsmängden i automaten har formen Q = Q₁ × Q₂, starttillståndet är tillståndet ⟨q₀, p₀⟩ och sluttillstånden är F₁ × F₂:

Sedan skapar vi övergångarna så att δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

I den här automaten går det till exempel från tillståndet ⟨q₀, p₀⟩ en övergång för symbolen 0 till tillståndet ⟨q₀,p₁⟩. Det betyder att automaten A₁ har en övergång för symbolen 0 från tillståndet q₀ tillbaka till q₀. Automaten A₂ har i sin tur en övergång för symbolen 0 från tillståndet p₀ till tillståndet p₁.

Vi kan pröva automaten. Den ska acceptera ord som 110 eller 00000 (de innehåller ett jämnt antal ettor och samtidigt ett udda antal nollor), men inte ord som 11, 111, 1010.

Källor

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