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.

Zdroje