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).