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

Zřetězení regulárních jazyků

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ějme dva regulární jazyky L1, L2. Dokážeme, že jejich zřetězení/konkatenace \(L = L_1 \circ L_2\) je také regulární jazyk.

Co je to konkatenace #

Zřetězením dvou slov „010“ a „1111“ vznikne slovo „0101111“. Zřetězením jazyků tak vznikne nový jazyk, který sestrojíme tak, že každé slovo z jednoho jazyka zřetězíme s každým slovem z jiného jazyka. Konkatenací dvou slov a dvou dvou jazyků budeme značit pomocí kolečka: \(\circ\). Pak můžeme definovat zřetězení jazyků L1 a L2 takto:

\[L_1 \circ L_2 = \left\{a\circ b\,|\, a\in L_1, b \in L_2\right\}\]

Idea důkazu #

Máme dva regulární jazyky L1, L2 a dva automaty, které tyto jazyky přijímají:

\begin{eqnarray} A_1&=&\left< Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left< Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Sestrojíme nedeterministický automat \(A=\left< Q, \Sigma, \delta, q, F\right>\), který bude „v sobě obsahovat“ oba automaty A1 a A2. Základní ideou je, že začneme slovo přijímat automatem A1 a když automat A1 dojde do koncového stavu, tak zbylou část slova zkusíme ještě přijmout automatem A2. Pokud i tento automat přijímá část slova, tak automat A slovo přijímá.

Příklad #

Mějme tento automat A1, který přijímá jen slova, která se skládají buď jen z 1 nebo jen z 0:

dále mějme tento automat, který přijímá slova, která končí na 01:

Automaty spojíme tak, že ze všech koncových stavů automatu A1 přidáme epsilon přechody do počátečního stavu automatu A2 a následně uděláme z koncových stavů A1 obyčejné stavy. Počáteční stav celého nového automatu bude počátečního stav automatu A1:

Jak bude automat fungovat? Začneme simulovat fungování automatu A1. Pokud přejdeme do bývalého koncového stavu q1 nebo q2 tak víme, že automat A1 přijímá část tohoto slova. Aby celé slovo bylo součástí jazyka \(L_1\circ L_2\), musí zbylou část slova ještě přijmout druhý automat A2 – proto ze všech bývalých koncových stavů vedou epsilon přechody do původního počátečního stavu automatu A2.

Pro příklad si vezměme slovo 0001. to patří do zřetězení obou jazyků, protože slovo může vzniknout zřetězením slov \(00 \circ 01\). Ale stejně tak může vzniknout zřetězením slov \(0\circ001\). V našem automatu můžeme nasimulovat oba postupy. Automat může postupovat touto cestou:

\[q_0 \rightarrow^0 q_1 \rightarrow^0 q_1 \rightarrow^{\varepsilon} p_0 \rightarrow^0 p_1 \rightarrow^1 p_2\]

Touto cestou by automat nejdřív „přijal“ část slova 00 a poté část slova 01. Nebo může postupovat touto cestou:

\[q_0 \rightarrow^0 q_1 \rightarrow^{\varepsilon} p_0 \rightarrow^0 p_0 \rightarrow^0 p_1 \rightarrow^1 p_2\]

a automat by tak nejdřív „přijal“ část slova 0 a pak část slova 001. V obou případech samozřejmě dojdeme do koncového stavu p2.

Formální postup #

Ještě jednou: Máme dva regulární jazyky L1, L2 a dva automaty, které tyto jazyky přijímají:

\begin{eqnarray} A_1&=&\left< Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left< Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Sestrojíme nedeterministický automat \(A=\left< Q, \Sigma, \delta, q, F\right>\), pro který platí:

  • \(Q = Q_1 \cup Q_2\) (zároveň předpokládáme, že \(Q_1 \cap Q_2 = \emptyset\))
  • \(\Sigma = \Sigma_1 \cup \Sigma_2\)
  • q = q0
  • F = F2

Přechodovou funkci δ sestavíme postupně:

\[\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\varepsilon\\\delta_1(q,a)\cup\left\{p_0\right\}&\mbox{pokud}&q\in F_1\wedge a=\varepsilon\\\delta_2(q,a)&\mbox{pokud}&q\in Q_2\end{cases}\]

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