Конкатенація регулярних мов

Нехай дано дві регулярні мови L₁, L₂. Доведемо, що їхня конкатенація $L = L_1 \circ L_2$ також є регулярною мовою.

Що таке конкатенація

Конкатенацією двох слів «010» і «1111» утворюється слово «0101111». Конкатенацію мов утворюємо так: кожне слово з однієї мови з'єднуємо з кожним словом з іншої мови, і виходить нова мова. Конкатенацію двох слів і двох мов позначатимемо кружечком: $\circ$. Тоді конкатенацію мов L₁ і L₂ означимо так:

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

Ідея доведення

Маємо дві регулярні мови L₁, L₂ та два автомати, що допускають ці мови:

\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}

Побудуємо недетермінований автомат $A=\left<Q, \Sigma, \delta, q, F\right>$, який «містить у собі» обидва автомати A₁ і A₂. Основна ідея така: починаємо обробляти слово автоматом A₁, а коли автомат A₁ доходить до заключного стану, решту слова ще пробуємо допустити автоматом A₂. Якщо й цей автомат допускає цю частину слова, то автомат A допускає слово.

Приклад

Нехай маємо автомат A₁, який допускає непорожні слова, що складаються лише з нулів, і слова, що складаються з одиниці, за якою йдуть лише нулі (1, 10, 100, …):

і автомат A₂, який допускає слова, що закінчуються на 01:

Автомати з'єднаємо так: з усіх заключних станів автомата A₁ додамо $\varepsilon$-переходи в початковий стан автомата A₂, а потім заключні стани A₁ зробимо звичайними станами. Початковим станом усього нового автомата буде початковий стан автомата A₁:

Як працюватиме автомат? Починаємо імітувати роботу автомата A₁. Якщо потрапляємо в колишній заключний стан q₁ або q₂, то знаємо, що автомат A₁ допускає частину цього слова. Щоб усе слово належало мові $L_1\circ L_2$, решту слова має ще допустити другий автомат A₂ — тому з усіх колишніх заключних станів ведуть $\varepsilon$-переходи у вихідний початковий стан автомата A₂.

Для прикладу візьмемо слово 0001. Воно належить конкатенації обох мов, бо може утворитися конкатенацією слів $00 \circ 01$. Але так само воно може утворитися конкатенацією слів $0\circ001$. У нашому автоматі можна імітувати обидва способи. Автомат може йти таким шляхом:

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

Цим шляхом автомат спершу «допустить» частину слова 00, а потім частину слова 01. Або він може йти таким шляхом:

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

і тоді автомат спершу «допустить» частину слова 0, а потім частину слова 001. В обох випадках ми, звісно, доходимо до заключного стану p₂.

Формальна побудова

Ще раз: маємо дві регулярні мови L₁, L₂ та два автомати, що допускають ці мови:

\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}

Побудуємо недетермінований автомат $A=\left<Q, \Sigma, \delta, q, F\right>$, для якого виконується:

• Q = Q₁ ∪ Q₂ (водночас припускаємо, що $Q_1 \cap Q_2 = \varnothing$)
• $\Sigma = \Sigma_1 \cup \Sigma_2$
• q = q₀
• F = F₂

Функцію переходів δ побудуємо поетапно:

$$ \delta(q, a) = \begin{cases} \delta_1(q,a)&\text{якщо}&q\in Q_1 \wedge q\notin F_1\\ \delta_1(q,a)&\text{якщо}&q\in F_1 \wedge a\ne\varepsilon\\ \delta_1(q,a)\cup\left\{p_0\right\}&\text{якщо}&q\in F_1\wedge a=\varepsilon\\ \delta_2(q,a)&\text{якщо}&q\in Q_2 \end{cases} $$

Джерела

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