Замикання Кліні регулярної мови
Нехай дано регулярну мову L. Доведемо, що замикання Кліні мови L знову є регулярною мовою.
Що таке замикання мови
Замикання Кліні мови L позначаємо L∗. Воно містить усі слова, які можна скласти конкатенацією скінченної кількості слів з мови L. Замикання можна означити так:
де ∘ позначає операцію конкатенації. Замикання містить і порожнє слово, тобто ϵ.
Формальна побудова
Діятимемо дуже схоже на випадок конкатенації мов. Тільки замість того, щоб з'єднувати два різні автомати, з'єднаємо один автомат: із заключних станів автомата проведемо ε-переходи в початковий стан цього автомата. Однак замикання має містити й порожнє слово. Як це забезпечити? Можна зробити початковий стан заключним. Тоді такий автомат допустив би порожнє слово, але міг би допустити й якісь інші слова, яких не повинен. Тому замість цього створимо новий початковий стан і проведемо з нього ε-перехід у вихідний початковий стан.
Маємо регулярну мову L1 та автомат, що допускає цю мову:
Побудуємо недетермінований автомат A = ⟨Q, Σ, δ, qs, F⟩, для якого виконується:
- Q = Q1 ∪ {qs}
- Σ= Σ1
- F = F1 ∪ {qs}
Функцію переходів δ означимо так:
Приклад
Нехай маємо автомат A1, який допускає слова 00 або 11:
Замикання Кліні мови L(A1) — це мова всіх слів, що складаються з пар 00 і 11, наприклад 0000, 110011, 11110000 тощо. Автомат, який допускав би це замикання, побудуємо так: створимо новий початковий стан qs з ε-переходом у колишній початковий стан q0 і додамо ε-переходи зі станів q3 і q4 у стан q0:
Можна перевірити, що цей автомат справді допускає слова 0000, 110011, 11110000, але не допустить, скажімо, слова 1010.
Джерела
Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови