Průnik regulárních jazyků

Kapitoly: Uzavřenost regulárních jazyků, Sjednocení, Průnik, Rozdíl, Doplněk, Zřetězení, Uzávěr

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

Idea důkazu

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

Slovo patří do průniku jazyků, pokud patří do jazyka L1 a zároveň L2. Tedy slovo musí přijímat automat A1 a zároveň automat A2. 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{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Sestrojíme automat $A=\left<Q, \Sigma, \delta, q, F\right>$, který přijímá jazyk L(A1)∩ L(A2). Platí, že

  • Q = Q1 × Q2
  • $\Sigma = \Sigma_1 \cap \Sigma_2$
  • q = <q0, p0>
  • F = F1 × F2

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

$$ \forall q\in Q_1, p\in Q_2: \delta(\left<q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right> $$

Příklad

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

a automat A2, který příjmá 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 = Q1 × Q2, počáteční stav je stav <q0, p0> a koncové stavy jsou F1 × F2:

Dále dotvoříme přechody tak, že δ(<q, p>, a) = <δ1(q, a), δ2(p, a)>:

V tomto automatu je například ze stavu <q0, p0> přechod pro symbol 0 do stavu <q0, p1>. Znamená to, že automat A1 má ze stavu q0 přechod pro symbol 0 zpět do stavu q0. Automat A2 má zase pro symbol 0 přechod ze stavu p0 do stavu p1.

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