Uzávěr regulárního jazyka

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^∗. 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 }=\{a_1\circ a_2\circ \cdots \circ a_n|a_i\in L,n\in {\mathbb{N}}_0\},$$

kde ∘ 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í jazyků. 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 L₁ a automat, který tento jazyk přijímá:

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\end{array}$$

Sestrojíme nedeterministický automat A = ⟨Q, Σ, δ, q_s, F⟩, pro který platí:

• Q = Q₁ ∪ {q_s}
• Σ= Σ₁
• F = F₁ ∪ {q_s}

Přechodovou funkci δ definujeme takto:

$$\delta (q,a)=\{\begin{array}{lll}{\delta }_1(q,a)& \text{pokud}& q\in Q_1\wedge q\notin F_1\\ {\delta }_1(q,a)& \text{pokud}& q\in F_1\wedge a\ne ϵ\\ {\delta }_1(q,a)\cup \left\{q_0\right\}& \text{pokud}& q\in F_1\wedge a=ϵ\\ \left\{q_0\right\}& \text{pokud}& q=q_s\wedge a=ϵ\\ \mathrm{\varnothing }& \text{pokud}& q=q_s\wedge a\ne ϵ\end{array}$$

Příklad

Mějme tento automat A₁, který přijímá slova 00 nebo 11:

Uzávěr jazyka L(A₁) 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 q_s s epsilon přechodem do bývalého počátečního stavu q₀ a přidali bychom epsilon přechody ze stavů q₃ a q₄ do stavu q₀:

Můžeme ověřit, že tento automat opravdu přijímá slova 0000, 110011, 11110000, ale nepřijme třeba slovo 1010.

Zdroje

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools