Об'єднання регулярних мов

Нехай дано дві регулярні мови L₁, L₂. Доведемо, що їхнє об'єднання L = L₁ ∪ L₂ також є регулярною мовою.

Побудова за допомогою детермінованого автомата

Ідея побудови

Маємо дві регулярні мови L₁ і L₂ та хочемо довести, що їхнє об'єднання L₁ ∪ L₂ знову є регулярною мовою. Оскільки L₁ і L₂ регулярні, існують скінченні автомати A₁ і A₂, які допускають мови L₁ і L₂, тобто L(A₁) = L₁ і L(A₂) = L₂. Далі ми побудуємо скінченний автомат A, що допускатиме мову L₁ ∪ L₂, і цим доведемо, що мова L₁ ∪ L₂ регулярна.

Як це зробити? Ми маємо скінченні автомати A₁ і A₂, які допускають окремі мови. Можемо сказати, що слово w належить мові L₁ ∪ L₂ тоді й лише тоді, коли його допускає принаймні один з автоматів A₁ або A₂.

Автомат A міг би працювати так: для вхідного слова w він імітує обчислення автомата A₁ на слові w. Якщо A₁ допускає слово w, то його допускає і A. Якщо A₁ слово w відхиляє, то A ще спробує імітувати обчислення A₂ на слові w. Якщо A₂ допускає слово w, то й A допускає слово w. В іншому разі A його відхиляє.

Залишилося формалізувати, що означає, що автомат A «імітує» обчислення іншого автомата.

Формалізація

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

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

Побудуємо скінченний автомат $A=\left<Q, \Sigma, \delta, q, F\right>$, який допускатиме мову L = L₁∪ L₂. Скористаємося ідеєю одночасної імітації двох автоматів A₁, A₂. Уявімо, що на вході маємо слово w = w₁w₂… w_n, і тепер одночасно імітуємо роботу автоматів A₁ і A₂ на слові w. Початкова конфігурація автомата A₁ — це <q₁, w₁w₂… w_n>, початкова конфігурація A₂ — це <q₂, w₁w₂… w_n>. У кожному автоматі тепер виконаємо крок обчислення і потрапимо в конфігурації <δ₁(q₁, w₁), w₂… w_n> та <δ₂(q₂, w₁), w₂… w_n>.

Бачимо, що ці конфігурації відрізняються лише першою компонентою, а другу — непрочитану частину слова — мають завжди однакову. Тому під час імітації нам не потрібно зберігати дві конфігурації двох автоматів, достатньо однієї конфігурації вигляду <<q_i, q_j>, w_l… w_n>, де q_i ∈ Q₁ і q_j ∈ Q₂. Іншими словами, початкова конфігурація автомата A, який ми будуємо, — це <<q₁, q₂>, w>. Перша частина пари <q₁, q₂> — це стан, у якому наразі перебуває автомат A₁, а друга компонента — поточний стан автомата A₂.

Отже, можемо записати, що множина станів автомата A дорівнює Q = Q₁ × Q₂. Це декартів добуток множин станів попередніх двох автоматів. Далі ідея така: автомат A матиме початковий стан <q₁, q₂>, і якщо автомат A₁ на символі w₁ переходить у стан q_i, а автомат A₂ на символі w₁ переходить у стан q_j, то автомат A на символі w₁ перейде у стан <q_i, q_j>.

Функцію переходів δ запишемо так (тут уже припускаємо, що наразі перебуваємо у станах q_i та q_j):

$$ \delta\left(\left<q_i, q_j\right>,w\right) = \left<\delta_1(q_i,w), \delta_2(q_j,w)\right> $$

Залишилося уточнити лише дрібниці. Для алфавіту маємо $\Sigma = \Sigma_1 \cup \Sigma_2$. Початковий стан дорівнює q = <q₁, q₂>. А заключними станами є всі пари <q_i, q_j>, такі що q_i ∈ F₁ або q_j ∈ F₂.

Ілюстрація побудови

Маємо два автомати. Перший — автомат A₁, що допускає всі слова (разом з порожнім словом), у яких чергуються нулі та одиниці, тобто слова вигляду 01, 0101, 010101, …

Другий автомат A₂ допускає слова, які містять принаймні один нуль:

Об'єднання цих мов — це слова, які або містять нуль, або мають вигляд 01, 0101, … Тепер побудуємо скінченний автомат $A=\left<Q, \Sigma, \delta, q, F\right>$, який допускатиме саме цю об'єднану мову. Спершу покажемо, як виглядатимуть стани нового автомата A. Це буде декартів добуток станів першого та другого автоматів:

$$ Q = Q_1 \times Q_2 = \left\{\left<q_0, p_0\right>, \left<q_0, p_1\right>, \left<q_1, p_0\right>, \left<q_1, p_1\right>, \left<q_2, p_0\right>, \left<q_2, p_1\right>\right\} $$

Так виглядають шість станів автомата A, який допускає об'єднану мову L(A₁) ∪ L(A₂). На діаграмі вони виглядали б так:

Не лякайся, що стани складаються з пар станів — це лише для кращої орієнтації в тому, що відбувається в автоматі. Стани цілком могли б мати звичайні назви q₀, …, q₅. Заключними є ті стани, що містять стан q₀ або p₁, а це заключні стани вихідних автоматів. Початковий стан — <q₀, p₀>.

Тепер потрібно знайти всі переходи. Складемо таку таблицю:

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$

І поступово заповнюватимемо її. Спершу з'ясуємо, куди веде перехід зі стану <q₀, p₀> на вході 0. З'ясуємо, куди веде перехід зі стану q₀ на вході 0 в автоматі A₁: він веде у стан q₁. В автоматі A₂ перехід із p₀ на нулі веде у стан p₁. Тому в таблицю запишемо <q₁, p₁>:

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$

На вході 1 отримаємо: для автомата A₁ маємо δ₁(q₀, 1) = q₂, а для автомата A₂ маємо δ₂(p₀, 1) = p₀. Отже, дістаємо стан <q₂, p₀>.

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>&\left<q_2, p_0\right>\\ \left<q_0, p_1\right>\\ \left<q_1, p_0\right>\\ \left<q_1, p_1\right>\\ \left<q_2, p_0\right>\\ \left<q_2, p_1\right>\\ \end{array} $$

Допишемо решту таблиці:

$$ \begin{array}{c|c|c} &0&1\\\hline \left<q_0, p_0\right>&\left<q_1, p_1\right>&\left<q_2, p_0\right>\\ \left<q_0, p_1\right>&\left<q_1, p_1\right>&\left<q_2, p_1\right>\\ \left<q_1, p_0\right>&\left<q_2, p_1\right>&\left<q_0, p_0\right>\\ \left<q_1, p_1\right>&\left<q_2, p_1\right>&\left<q_0, p_1\right>\\ \left<q_2, p_0\right>&\left<q_2,p_1\right>&\left<q_2, p_0\right>\\ \left<q_2, p_1\right>&\left<q_2,p_1\right>&\left<q_2,p_1\right>\\ \end{array} $$

А за цією таблицею залишилося домалювати решту діаграми.

Можемо перевірити, чи автомат працює як слід. Спробуємо допустити слово 0100. Автомат послідовно проходить стани

$$ \left<q_0, p_0\right>, \left<q_1, p_1\right>, \left<q_0, p_1\right>, \left<q_1, p_1\right>, \left<q_2, p_1\right> $$

Оскільки стан <q₂, p₁> заключний, автомат A допускає слово 0100. Що було б, якби ми спробували допустити слово 0100 автоматами A₁ і A₂? Автомат A₁ послідовно пройшов би такі стани:

$$ q_0, q_1, q_0, q_1, q_2 $$

Автомат закінчив у стані q₂, який не є заключним, тож автомат A₁ це слово не допустив би. А автомат A₂?

$$ p_0, p_1, p_1, p_1, p_1 $$

Стан p₁ заключний, тож автомат A₂ слово 0100 допустив би. Зверни увагу: автомати A₁ і A₂ закінчили у станах q₂ і p₁, що узгоджується з тим, що автомат A закінчив у стані <q₂, p₁>.

Побудова за допомогою недетермінованого автомата

Приклад

Те, що множина регулярних мов замкнена відносно об'єднання, можна довести і побудовою недетермінованого автомата, який буде значно простішим.

Отже, маємо дві регулярні мови L₁, L₂ і хочемо довести, що їхнє об'єднання L = L₁ ∪ L₂ також є регулярною мовою. Оскільки L₁, L₂ регулярні, мають існувати автомати A₁, A₂, що допускають ці мови. Тобто L(A₁) = L₁ і L(A₂) = L₂. За допомогою цих автоматів побудуємо автомат A, який допускатиме мову L, тобто L(A) = L.

Припустімо, що скінченні автомати A₁ і A₂ виглядають так:

та

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

Формалізація

Маємо два автомати $A_1=\left<Q_1, \Sigma, \delta_1, q_1, F_1\right>$ і $A_2=\left<Q_2, \Sigma, \delta_2, q_2, F_2\right>$. Побудуємо автомат $A=\left<Q, \Sigma, \delta, q_0, F\right>$, який допускатиме об'єднання мов, що допускаються попередніми автоматами, тобто L(A) = L(A₁)∪ L(A₂). При цьому:

• Q = Q₁ ∪ Q₂ ∪ {q₀}
• F = F₁ ∪ F₂

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

$$ \delta(q,a)= \begin{cases} \delta_1(q,a)&\text{якщо}&q\in Q_1\\ \delta_2(q,a)&\text{якщо}&q\in Q_2\\ \left\{q_1, q_2\right\}&\text{якщо}&q=q_0 \wedge a=\varepsilon\\ \varnothing&\text{якщо}&q=q_0\wedge a\ne\varepsilon \end{cases} $$

Джерела

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