Конкатенація регулярних мов
Нехай дано дві регулярні мови L1, L2. Доведемо, що їхня конкатенація L = L1 ∘ L2 також є регулярною мовою.
Що таке конкатенація
Конкатенацією двох слів «010» і «1111» утворюється слово «0101111». Конкатенацію мов утворюємо так: кожне слово з однієї мови з'єднуємо з кожним словом з іншої мови, і виходить нова мова. Конкатенацію двох слів і двох мов позначатимемо кружечком: ∘. Тоді конкатенацію мов L1 і L2 означимо так:
Ідея доведення
Маємо дві регулярні мови L1, L2 та два автомати, що допускають ці мови:
Побудуємо недетермінований автомат A = ⟨Q, Σ, δ, q, F⟩, який «містить у собі» обидва автомати A1 і A2. Основна ідея така: починаємо обробляти слово автоматом A1, а коли автомат A1 доходить до заключного стану, решту слова ще пробуємо допустити автоматом A2. Якщо й цей автомат допускає цю частину слова, то автомат A допускає слово.
Приклад
Нехай маємо автомат A1, який допускає непорожні слова, що складаються лише з нулів, і слова, що складаються з одиниці, за якою йдуть лише нулі (1, 10, 100, …):
і автомат A2, який допускає слова, що закінчуються на 01:
Автомати з'єднаємо так: з усіх заключних станів автомата A1 додамо ε-переходи в початковий стан автомата A2, а потім заключні стани A1 зробимо звичайними станами. Початковим станом усього нового автомата буде початковий стан автомата A1:
Як працюватиме автомат? Починаємо імітувати роботу автомата A1. Якщо потрапляємо в колишній заключний стан q1 або q2, то знаємо, що автомат A1 допускає частину цього слова. Щоб усе слово належало мові L1 ∘ L2, решту слова має ще допустити другий автомат A2 — тому з усіх колишніх заключних станів ведуть ε-переходи у вихідний початковий стан автомата A2.
Для прикладу візьмемо слово 0001. Воно належить конкатенації обох мов, бо може утворитися конкатенацією слів 00 ∘ 01. Але так само воно може утворитися конкатенацією слів 0 ∘ 001. У нашому автоматі можна імітувати обидва способи. Автомат може йти таким шляхом:
Цим шляхом автомат спершу «допустить» частину слова 00, а потім частину слова 01. Або він може йти таким шляхом:
і тоді автомат спершу «допустить» частину слова 0, а потім частину слова 001. В обох випадках ми, звісно, доходимо до заключного стану p2.
Формальна побудова
Ще раз: маємо дві регулярні мови L1, L2 та два автомати, що допускають ці мови:
Побудуємо недетермінований автомат A = ⟨Q, Σ, δ, q, F⟩, для якого виконується:
- Q = Q1 ∪ Q2 (водночас припускаємо, що Q1 ∩ Q2 = ∅)
- Σ= Σ1 ∪ Σ2
- q = q0
- F = F2
Функцію переходів δ побудуємо поетапно:
Джерела
Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови