Reguláris nyelvek metszete

Legyen adott két reguláris nyelv, L₁, L₂. Bebizonyítjuk, hogy a metszetük, L = L₁ ∩ L₂ is reguláris nyelv.

A bizonyítás ötlete

Adott két reguláris nyelv, L₁ és L₂, és be akarjuk bizonyítani, hogy az L₁ ∩ L₂ metszet 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.

Egy szó akkor tartozik a nyelvek metszetébe, ha az L₁ és egyben az L₂ nyelvnek is eleme. A szót tehát az A₁ és egyben az A₂ automatának is el kell fogadnia. Pontosan ugyanazt az ötletet használjuk, mint a reguláris nyelvek uniójánál, csak a végállapotok halmazát változtatjuk meg.

Az eljárás formalizálása

Adott két automata,

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

Megszerkesztjük az A = ⟨Q, Σ, δ, q, F⟩ automatát, amely az L(A₁) ∩ L(A₂) nyelvet fogadja el. Teljesül, hogy

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

A δ átmeneti függvényre a következő összefüggés teljesül:

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

Példa

Adott ez az A₁ automata, amely elfogadja az összes olyan szót, amelyben páros számú 1 van:

és az A₂ automata, amely a páratlan számú 0-t tartalmazó szavakat fogadja el:

Megszerkesztjük azt az automatát, amely e nyelvek metszetét fogadja el. Ennek az automatának az állapothalmaza Q = Q₁ × Q₂, a kezdőállapot a ⟨q₀, p₀⟩ állapot, a végállapotok pedig F₁ × F₂:

Ezután megrajzoljuk az átmeneteket úgy, hogy δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

Ebben az automatában például a ⟨q₀, p₀⟩ állapotból a 0 szimbólumra a ⟨q₀,p₁⟩ állapotba vezet átmenet. Ez azt jelenti, hogy az A₁ automatában a q₀ állapotból a 0 szimbólumra visszavezet átmenet a q₀ állapotba. Az A₂ automatában pedig a 0 szimbólumra a p₀ állapotból a p₁ állapotba vezet átmenet.

Az automatát ki is próbálhatjuk. El kell fogadnia az olyan szavakat, mint a 110 vagy a 00000 (páros számú 1-et és egyben páratlan számú 0-t tartalmaznak), de nem szabad elfogadnia az olyan szavakat, mint a 11, 111, 1010.

Források

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