Sjednocení 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 sjednocení L = L1 ∪ L2 je také regulární jazyk.
Postup pomocí deterministického automatu
Idea postupu
Máme dva regulární jazyky L1 a L2 a chceme dokázat, že jejich sjednocení 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í.
Jak to provedeme? Máme po ruce konečné automaty A1 a A2, které přijímají jednotlivé jazyky. Můžeme říci, že slovo w patří do jazyka L1 ∪ L2 právě tehdy, pokud ho přijme alespoň jeden z automatů A1 nebo A2.
Automat A by mohl fungovat tak, že pro vstup w bude simulovat výpočet automatu A1 pro vstup w. Pokud A1 slovo w přijme, tak slovo w přijme i A. Pokud A1 slovo w zamítne, tak A ještě zkusí simulovat výpočet A2 pro vstup w. Pokud A2 přijme slovo w, tak i A přijme slovo w. V opačném případě zamítne.
Zbývá nám formalizovat co to znamená, že automat A „simuluje“ výpočet jiného automatu.
Formalizace
Máme dva regulární jazyky L1 a L2, které jsou přijímány konečnými automaty
\begin{eqnarray} A_1 &=& \left<Q_1, \Sigma_1, \delta_1, q_1, F_1\right>\\ A_2 &=& \left<Q_2, \Sigma_2, \delta_2, q_2, F_2\right>. \end{eqnarray}
Sestavíme konečný automat $A=\left<Q, \Sigma, \delta, q, F\right>$, který bude přijímat jazyk L = L1∪ L2. Využijeme ideu simulování dvou automatů A1, A2. Představme si tak, že máme na vstupu slovo w = w1w2… wn a nyní bude současně simulovat průběh automatů A1 a A2 pro slovo w. Počáteční konfirace automatu A1 je <q1, w1w2… wn>, počáteční konfigurace A2 je <q2, w1w2… wn>. V každém automatu nyní provedeme krok výpočtu, čímž se dostaneme do konfigurací <δ1(q1, w1), w2… wn> a <δ2(q2, w1), w2… wn>.
Vidíme, že tyto konfigurace se liší jen v první složce, druhou — nepřečtenou část slova — mají vždy stejnou. Během simulace tak nemusíme udržovat dvě konfigurace dvou automatů, ale stačí nám jedna konfigurace tvaru <<qi, qj>, wl… wn>, kde qi ∈ Q1 a qj ∈ Q2. Jinými slovy náš sestavovaný automat A bude mít počáteční konfiguraci <<q1, q2>, w>. První část dvojice <q1, q2> představuje stav, ve kterém se aktuálně nachází automat A1 a druhá složka představuje aktuální stav automatu A2.
Můžeme tak napsat, že sestavovaný automat A bude mít množinu stavů rovnou Q = Q1 × Q2. Bude to kartézský součin stavů z předchozích dvou automatů. Následující idea je taková, že automat A bude mít počáteční stav <q1, q2> a pokud automat A1 přejde pro symbol w1 do stavu qi a automat A2 přejde pro symbol w1 do stavu qj, tak automat A přejde pro symbol w1 do stavu <qi, qj>.
Přechodovu funkci δ zapíšeme takto (zde už předpokládáme, že jsme aktuálně ve stavech qi a qj):
$$ \delta\left(\left<q_i, q_j\right>,w\right) = \left<\delta_1(q_i,w), \delta_2(q_j,w)\right> $$
Zbývá vyřešit už jen drobnosti. Pro abecedu platí $\Sigma = \Sigma_1 \cup \Sigma_2$. Počáteční stav je roven q = <q1, q2>. A koncové stavy jsou všechny dvojice <qi, qj> takové, že buď qi ∈ F1 nebo qj ∈ F2.
Ilustrace postupu
Mějme dva automaty. První je automat A1, který přijímá všechna slova (včetně prázdného slova), kde se střídají nuly a jedničky, tj. slova tvaru 01, 0101, 010101, …
Další automat A2 přijímá slova, která obsahují alespoň jednu nulu:
Sjednocení těchto jazyků jsou slova, která buď obsahují nulu nebo jsou tvaru 01, 0101, … Nyní sestavíme konečný automat $A=\left<Q, \Sigma, \delta, q, F\right>$, který bude přijímat právě tento sjednocený jazyk. Jako první si ukážeme, jak budou vypadat stavy tohoto nového automatu A. Bude to kartézský součin stavů prvního a druhého automatu:
$$ Q = Q_1 \times Q_2 = \left\{\left<q_0, p_0\right>, \left<q_0, p_1\right>, \left<q_1, p_0\right>, \left<q_1, p_1\right>, \left<q_2, p_0\right>, \left<q_2, p_1\right>\right\} $$
Takto vypadá šest stavů automatu A, který přijímá sjednocený jazyk L(A1) ∪ L(A2). V diagramu by vypadaly takto:
Nijak se nelekněte, že tam máme stavy, které se skládají z dvojic stavů — slouží to jen k lepší orientaci toho, co se vlatně v automatu děje. Stavy by se klidně mohly jmenovat klasicky q0, …, q5. Koncové stavy jsou ty stavy, které obsahují buď stav q0 nebo p1, což jsou koncové stavy původních automatů. Počáteční stav je <p0, q0>.
Nyní musíme najít všechny přechody. Napíšeme si takovout tabulku:
$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$
A postupně budeme tabulku doplňovat. Jako první zjistíme, kam povede přechod ze stavu <q0, p0> při vstupu 0. Zjistíme, kam vede přechod ze stavu q0 při vstupu 0 v automatu A1: ten vede do stavu q1. V automatu A2 vede přechod z p0 při nule do stavu p1. Takže v do tabulky zapíšeme <q1, p1>:
$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$
Při vstupu 1 dostaneme: pro automat A1 máme δ1(q0, 1) = q2 a pro automat A2 máme δ2(p0, 1) = p0. Získáme tak stav <q2, p0>.
$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>&\left<q_2, p_0\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$
Dopíšeme zbytek tabulky:
$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>&\left<q_2, p_0\right>\\ \left<q_0, p_1\right>&\left<q_1, p_1\right>&\left<q_2, p_1\right>\\ \left<q_1, p_0\right>&\left<q_2, p_1\right>&\left<q_0, p_0\right>\\ \left<q_1, p_1\right>&\left<q_2, p_1\right>&\left<q_0, p_1\right>\\ \left<q_2, p_0\right>&\left<q_2,p_1\right>&\left<q_2, p_0\right>\\ \left<q_2, p_1\right>&\left<q_2,p_1\right>&\left<q_2,p_1\right>\\ \end{array} $$
A podle této tabulky už jen dokreslíme zbytek diagramu.
Můžeme si vyzkoušet, že automat funguje jak má. Zkusíme přijmout slovo 0100. Automat postupně projde stavy
$$ \left<q_0, p_0\right>, \left<q_1, p_1\right>, \left<q_0, p_1\right>, \left<q_1, p_1\right>, \left<q_2, p_1\right> $$
Protože stav <q2, p1> je koncový stav, tak automat A přijímá slovo 0100. Jak by to dopadlo, kdybychom zkusili slovo 0100 přijmout automaty A1 a A2? Automat A1 by postupně prošel těmito stavy:
$$ q_0, q_1, q_0, q_1, q_2 $$
Automat skončil ve stavu q2, který není koncový, takže toto slovo by automat A1 nepřijal. Co automat A2?
$$ p_0, p_1, p_1, p_1, p_1 $$
Stav p1 je koncový, takže automat A2 by slovo 0100 přijal. Všiměnte si, že automaty A1 a A2 skončili ve stavech q2 a p1, což je v souladu s tím, že automat A skončil ve stavu <q2, p1>.
Postup pomocí nedeterministického automatu
Příklad
Že je množina regulárních jazyků uzavřená na sjednocení si můžeme dokázat i sestrojením nedeterministického automatu, který bude mnohem jednodušší.
Máme tak dva regulární jazyky L1, L2 a chceme dokázat, že jejich sjednocení L = L1 ∪ L2 je také regulární jazyk. Protože L1, L2 jsou regulární jazyky, musí existovat automaty A1, A2, které tyto jazyky přijímají. Tj. platí, že L(A1) = L1 a L(A2) = L2. Pomocí těchto automatů sestrojíme automat A, který bude přijímat jazyk L, tj. L(A) = L.
Předpokládejme, že konečné automaty A1 a A2 vypadají takto:
a
Automat, který by přijímal sjednocení obou jazyků bychom sestrojili tak, že bychom vytvořili nový počáteční stav a z tohoto stavu bychom vedli dva epsilon přechody do původních počátečních stavů. To je celé. Automat by vypadal takto:
Formalizace
Máme dva automaty $A_1=\left<Q_1, \Sigma, \delta_1, q_1, F_1\right>$ a $A_2=\left<Q_2, \Sigma, \delta_2, q_2, F_2\right>$. Sestrojíme automat $A=\left<Q, \Sigma, \delta, q_0, F\right>$, který bude přijímat sjednocení jazyků, které jsou přijímany předchozími automaty, tj. L(A) = L(A1)∪ L(A2). Přitom platí:
- Q = Q1 ∪ Q2 ∪ {q0}
- F = F1 ∪ F2
A přechodovu δ funkci definujeme takto:
$$ \delta(q,a)= \begin{cases} \delta_1(q,a)&\mbox{pokud}&q\in Q_1\\ \delta_2(q,a)&\mbox{pokud}&q\in Q_2\\ \left\{q_1, q_2\right\}&\mbox{pokud}&q=q_0 \wedge a=\varepsilon\\ \emptyset&\mbox{pokud}&q=q_0\wedge a\ne\varepsilon \end{cases} $$