Průnik regulárních jazyků

Mějme dva regulární jazyky L₁, L₂. Dokážeme, že jejich průnik L = L₁ ∩ L₂ je také regulární jazyk.

Idea důkazu

Máme dva regulární jazyky L₁ a L₂ a chceme dokázat, že jejich průnik L₁ ∩ L₂ je opět regulární jazyk. Protože L₁ a L₂ jsou regulární jazyky, tak existují konečné automaty A₁ a A₂, které přijímají jazyky L₁ a L₂, tedy platí L(A₁) = L₁ a L(A₂) = L₂. My dále sestavíme konečný automat A, který bude přijímat jazyk L₁ ∩ L₂, čímž dokážeme, že jazyk L₁ ∩ L₂ je regulární.

Slovo patří do průniku jazyků, pokud patří do jazyka L₁ a zároveň L₂. Tedy slovo musí přijímat automat A₁ a zároveň automat A₂. Využijeme úplně stejnou ideu, jakou jsme využili u sjednocení regulárních jazyků, pouze změníme množinu koncových stavů.

Formalizace postupu

Máme dva automaty,

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

Sestrojíme automat A = ⟨Q, Σ, δ, q, F⟩, který přijímá jazyk L(A₁) ∩ L(A₂). Platí, že

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

Pro přechodovou funkci δ bude platit následující vztah:

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

Příklad

Mějme tento automat A₁, který přijímá všechna slova, která obsahují sudý počet 1:

a automat A₂, který přijímá slova obsahující lichý počet 0:

Sestrojíme automat, který bude přijímat průnik těchto jazyků. Množina stavů tohoto automatu má tvar Q = Q₁ × Q₂, počáteční stav je stav ⟨q₀, p₀⟩ a koncové stavy jsou F₁ × F₂:

Dále dotvoříme přechody tak, že δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

V tomto automatu je například ze stavu ⟨q₀, p₀⟩ přechod pro symbol 0 do stavu ⟨q₀,p₁⟩. Znamená to, že automat A₁ má ze stavu q₀ přechod pro symbol 0 zpět do stavu q₀. Automat A₂ má zase pro symbol 0 přechod ze stavu p₀ do stavu p₁.

Automat si můžeme vyzkoušet. Měl by přijímat slova jako 110 nebo 00000 (obsahují sudý počet 1 a zároveň lichý počet 0), ale neměl by přijímat slova jako 11, 111, 1010.

Zdroje

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