Uzávěr regulárního jazyka
Kapitoly: Uzavřenost regulárních jazyků, Sjednocení, Průnik, Rozdíl, Doplněk, Zřetězení, Uzávěr
Máme regulární jazyk L. Dokážeme, že uzávěr jazyka L je opět regulární jazyk.
Co je to uzávěr jazyka
Uzávěr jazyka L značíme jako $L^\ast$. Uzávěr obsahuje všechna slova, která jde poskládat zřetězením konečného množství slov z jazyka L. Uzávěr můžeme definovat jako:
$$ L^\ast = \left\{a_1\circ a_2 \circ \dots \circ a_n ,|, a_i \in L, n \in \mathbb{N}_0 \right\}, $$
kde $\circ$ značí operaci zřetězení. Uzávěr obsahuje i prázdné slovo, tj. ε.
Formální postup
Budeme postupovat velmi podobně jako v případě zřetězení jazyka. Jenom místo toho, abychom propojovali dva různé automaty, propojíme jeden automat — z koncových stavů automatu tak povedeme epsilon přechody do počátečního stavu automatu. Nicméně uzávěr musí obsahovat i prázdné slovo. Jak to zařídit? Můžeme z počátečního stavu udělat koncový stav. Pak by takový automat přijal prázdné slovo, ale mohl by přijmout i nějaké další slovo. Proto místo toho vytvoříme nový počáteční stav a z tohoto nového počátečního stavu povedeme epsilon přechod do původního počátečního stavu.
Máme regulární jazyk L1 a automat, který tento jazyk přijímá:
\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \end{eqnarray}
Sestrojíme nedeterministický automat $A=\left<Q, \Sigma, \delta, q_s, F\right>$, pro který platí:
- Q = Q1 ∪ {qs}
- $\Sigma = \Sigma_1$
- F = F1 ∪ {qs}
Přechodovou funkci δ definujeme takto:
$$ \delta(q, a) = \begin{cases} \delta_1(q, a)&\mbox{pokud}&q\in Q_1 \wedge q\notin F_1\\ \delta_1(q, a)&\mbox{pokud}&q\in F_1 \wedge a\ne \epsilon\\ \delta_1(q, a)\cup\left\{q_0\right\}&\mbox{pokud}&q\in F_1 \wedge a= \epsilon\\ \left\{q_0\right\}&\mbox{pokud}&q=q_s \wedge a= \epsilon\\ \emptyset&\mbox{pokud}&q=q_s \wedge a\ne \epsilon\\ \end{cases} $$
Příklad
Mějme tento automat A1, který přijímá slova 00 nebo 11:
Uzávěr jazyka L(A1) je tak jazyk všech slov, které se skládají z dvojic 00 a 11, například 0000, 110011, 11110000 atp. Automat, který by tento uzávěr přijímal bychom sestavili tak, že bychom vytvořili nový počáteční stav qs s epsilon přechodem do bývalého počátečního stavu q0 a přidali bychom epsilon přechody ze stavů q3 a q4 do stavu q0:
Můžeme ověřit, že tento automat opravdu přijímá slova 0000, 110011, 11110000, ale nepřijme třeba slova 1010.