Об'єднання регулярних мов
Нехай дано дві регулярні мови L1, L2. Доведемо, що їхнє об'єднання L = L1 ∪ L2 також є регулярною мовою.
Побудова за допомогою детермінованого автомата
Ідея побудови
Маємо дві регулярні мови L1 і L2 та хочемо довести, що їхнє об'єднання L1 ∪ L2 знову є регулярною мовою. Оскільки L1 і L2 регулярні, існують скінченні автомати A1 і A2, які допускають мови L1 і L2, тобто L(A1) = L1 і L(A2) = L2. Далі ми побудуємо скінченний автомат A, що допускатиме мову L1 ∪ L2, і цим доведемо, що мова L1 ∪ L2 регулярна.
Як це зробити? Ми маємо скінченні автомати A1 і A2, які допускають окремі мови. Можемо сказати, що слово w належить мові L1 ∪ L2 тоді й лише тоді, коли його допускає принаймні один з автоматів A1 або A2.
Автомат A міг би працювати так: для вхідного слова w він імітує обчислення автомата A1 на слові w. Якщо A1 допускає слово w, то його допускає і A. Якщо A1 слово w відхиляє, то A ще спробує імітувати обчислення A2 на слові w. Якщо A2 допускає слово w, то й A допускає слово w. В іншому разі A його відхиляє.
Залишилося формалізувати, що означає, що автомат A «імітує» обчислення іншого автомата.
Формалізація
Маємо дві регулярні мови L1 і L2, які допускаються скінченними автоматами
Побудуємо скінченний автомат A = ⟨Q, Σ, δ, q, F⟩, який допускатиме мову L = L1 ∪ L2. Скористаємося ідеєю одночасної імітації двох автоматів A1, A2. Уявімо, що на вході маємо слово w = w1w2… wn, і тепер одночасно імітуємо роботу автоматів A1 і A2 на слові w. Початкова конфігурація автомата A1 — це ⟨q1, w1w2… wn⟩, початкова конфігурація A2 — це ⟨q2, w1w2… wn⟩. У кожному автоматі тепер виконаємо крок обчислення і потрапимо в конфігурації ⟨δ1(q1, w1), w2… wn⟩ та ⟨δ2(q2, w1), w2… wn⟩.
Бачимо, що ці конфігурації відрізняються лише першою компонентою, а другу — непрочитану частину слова — мають завжди однакову. Тому під час імітації нам не потрібно зберігати дві конфігурації двох автоматів, достатньо однієї конфігурації вигляду ⟨⟨qi, qj⟩, wl… wn⟩, де qi ∈ Q1 і qj ∈ Q2. Іншими словами, початкова конфігурація автомата A, який ми будуємо, — це ⟨⟨q1, q2⟩, w⟩. Перша частина пари ⟨q1, q2⟩ — це стан, у якому наразі перебуває автомат A1, а друга компонента — поточний стан автомата A2.
Отже, можемо записати, що множина станів автомата A дорівнює Q = Q1 × Q2. Це декартів добуток множин станів попередніх двох автоматів. Далі ідея така: автомат A матиме початковий стан ⟨q1, q2⟩, і якщо автомат A1 на символі w1 переходить у стан qi, а автомат A2 на символі w1 переходить у стан qj, то автомат A на символі w1 перейде у стан ⟨qi, qj⟩.
Функцію переходів δ запишемо так (тут уже припускаємо, що наразі перебуваємо у станах qi та qj):
Залишилося уточнити лише дрібниці. Для алфавіту маємо Σ= Σ1 ∪ Σ2. Початковий стан дорівнює q = ⟨q1, q2⟩. А заключними станами є всі пари ⟨qi, qj⟩, такі що qi ∈ F1 або qj ∈ F2.
Ілюстрація побудови
Маємо два автомати. Перший — автомат A1, що допускає всі слова (разом з порожнім словом), у яких чергуються нулі та одиниці, тобто слова вигляду 01, 0101, 010101, …
Другий автомат A2 допускає слова, які містять принаймні один нуль:
Об'єднання цих мов — це слова, які або містять нуль, або мають вигляд 01, 0101, … Тепер побудуємо скінченний автомат A = ⟨Q, Σ, δ, q, F⟩, який допускатиме саме цю об'єднану мову. Спершу покажемо, як виглядатимуть стани нового автомата A. Це буде декартів добуток станів першого та другого автоматів:
Так виглядають шість станів автомата A, який допускає об'єднану мову L(A1) ∪ L(A2). На діаграмі вони виглядали б так:
Не лякайся, що стани складаються з пар станів — це лише для кращої орієнтації в тому, що відбувається в автоматі. Стани цілком могли б мати звичайні назви q0, …, q5. Заключними є ті стани, що містять стан q0 або p1, а це заключні стани вихідних автоматів. Початковий стан — ⟨q0, p0⟩.
Тепер потрібно знайти всі переходи. Складемо таку таблицю:
І поступово заповнюватимемо її. Спершу з'ясуємо, куди веде перехід зі стану ⟨q0, p0⟩ на вході 0. З'ясуємо, куди веде перехід зі стану q0 на вході 0 в автоматі A1: він веде у стан q1. В автоматі A2 перехід із p0 на нулі веде у стан p1. Тому в таблицю запишемо ⟨q1, p1⟩:
На вході 1 отримаємо: для автомата A1 маємо δ1(q0, 1) = q2, а для автомата A2 маємо δ2(p0, 1) = p0. Отже, дістаємо стан ⟨q2, p0⟩.
Допишемо решту таблиці:
А за цією таблицею залишилося домалювати решту діаграми.
Можемо перевірити, чи автомат працює як слід. Спробуємо допустити слово 0100. Автомат послідовно проходить стани
Оскільки стан ⟨q2, p1⟩ заключний, автомат A допускає слово 0100. Що було б, якби ми спробували допустити слово 0100 автоматами A1 і A2? Автомат A1 послідовно пройшов би такі стани:
Автомат закінчив у стані q2, який не є заключним, тож автомат A1 це слово не допустив би. А автомат A2?
Стан p1 заключний, тож автомат A2 слово 0100 допустив би. Зверни увагу: автомати A1 і A2 закінчили у станах q2 і p1, що узгоджується з тим, що автомат A закінчив у стані ⟨q2, p1⟩.
Побудова за допомогою недетермінованого автомата
Приклад
Те, що множина регулярних мов замкнена відносно об'єднання, можна довести і побудовою недетермінованого автомата, який буде значно простішим.
Отже, маємо дві регулярні мови L1, L2 і хочемо довести, що їхнє об'єднання L = L1 ∪ L2 також є регулярною мовою. Оскільки L1, L2 регулярні, мають існувати автомати A1, A2, що допускають ці мови. Тобто L(A1) = L1 і L(A2) = L2. За допомогою цих автоматів побудуємо автомат A, який допускатиме мову L, тобто L(A) = L.
Припустімо, що скінченні автомати A1 і A2 виглядають так:
та
Автомат, що допускає об'єднання обох мов, побудуємо так: створимо новий початковий стан і проведемо з нього два ε-переходи в обидва вихідні початкові стани. Це все. Автомат виглядатиме так:
Формалізація
Маємо два автомати A1 = ⟨Q1, Σ, δ1, q1, F1⟩ і A2 = ⟨Q2, Σ, δ2, q2, F2⟩. Побудуємо автомат A = ⟨Q, Σ, δ, q0, F⟩, який допускатиме об'єднання мов, що допускаються попередніми автоматами, тобто L(A) = L(A1) ∪ L(A2). При цьому:
- Q = Q1 ∪ Q2 ∪ {q0}
- F = F1 ∪ F2
А функцію переходів δ означимо так:
Джерела
Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови