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

Mějme dva regulární jazyky L₁, L₂. 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ů L₁ a L₂ 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 L₁, L₂ 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 A₁ a A₂. Základní ideou je, že začneme slovo přijímat automatem A₁ a když automat A₁ dojde do koncového stavu, tak zbylou část slova zkusíme ještě přijmout automatem A₂. Pokud i tento automat přijímá část slova, tak automat A slovo přijímá.

Příklad

Mějme tento automat A₁, 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 A₁ přidáme epsilon přechody do počátečního stavu automatu A₂ a následně uděláme z koncových stavů A₁ obyčejné stavy. Počáteční stav celého nového automatu bude počátečního stav automatu A₁:

Jak bude automat fungovat? Začneme simulovat fungování automatu A₁. Pokud přejdeme do bývalého koncového stavu q₁ nebo q₂ tak víme, že automat A₁ 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 A₂ — proto ze všech bývalých koncových stavů vedou epsilon přechody do původního počátečního stavu automatu A₂.

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 p₂.

Formální postup

Ještě jednou: Máme dva regulární jazyky L₁, L₂ 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₁ ∪ Q₂ (zároveň předpokládáme, že Q₁ ∩ Q₂ = ∅)
• $\Sigma = \Sigma_1 \cup \Sigma_2$
• q = q₀
• F = F₂

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

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