Замикання Кліні регулярної мови

Нехай дано регулярну мову L. Доведемо, що замикання Кліні мови L знову є регулярною мовою.

Що таке замикання мови

Замикання Кліні мови L позначаємо $L^\ast$. Воно містить усі слова, які можна скласти конкатенацією скінченної кількості слів з мови L. Замикання можна означити так:

$$ L^\ast = \left\{a_1\circ a_2 \circ \dots \circ a_n ,|, a_i \in L, n \in \mathbb{N}_0 \right\}, $$

де $\circ$ позначає операцію конкатенації. Замикання містить і порожнє слово, тобто ε.

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

Діятимемо дуже схоже на випадок конкатенації мов. Тільки замість того, щоб з'єднувати два різні автомати, з'єднаємо один автомат: із заключних станів автомата проведемо $\varepsilon$-переходи в початковий стан цього автомата. Однак замикання має містити й порожнє слово. Як це забезпечити? Можна зробити початковий стан заключним. Тоді такий автомат допустив би порожнє слово, але міг би допустити й якісь інші слова, яких не повинен. Тому замість цього створимо новий початковий стан і проведемо з нього $\varepsilon$-перехід у вихідний початковий стан.

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

\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right> \end{eqnarray}

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

• Q = Q₁ ∪ {q_s}
• $\Sigma = \Sigma_1$
• F = F₁ ∪ {q_s}

Функцію переходів δ означимо так:

$$ \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 \epsilon\\ \delta_1(q, a)\cup\left\{q_0\right\}&\text{якщо}&q\in F_1 \wedge a= \epsilon\\ \left\{q_0\right\}&\text{якщо}&q=q_s \wedge a= \epsilon\\ \varnothing&\text{якщо}&q=q_s \wedge a\ne \epsilon\\ \end{cases} $$

Приклад

Нехай маємо автомат A₁, який допускає слова 00 або 11:

Замикання Кліні мови L(A₁) — це мова всіх слів, що складаються з пар 00 і 11, наприклад 0000, 110011, 11110000 тощо. Автомат, який допускав би це замикання, побудуємо так: створимо новий початковий стан q_s з $\varepsilon$-переходом у колишній початковий стан q₀ і додамо $\varepsilon$-переходи зі станів q₃ і q₄ у стан q₀:

Можна перевірити, що цей автомат справді допускає слова 0000, 110011, 11110000, але не допустить, скажімо, слова 1010.

Джерела

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