PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Uzávěr regulárního jazyka

Zobrazit kapitoly článku
  1. Uzavřenost regulárních jazyků
  2. Sjednocení
  3. Průnik
  4. Rozdíl
  5. Doplněk
  6. Zřetězení
  7. 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 = Q_1 \cup \left\{q_s\right\}\)
  • \(\Sigma = \Sigma_1\)
  • \(F = F_1 \cup \left\{q_s\right\}\)

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 #

 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace