✖

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

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

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

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

L∗={a1∘a2∘⋯∘an|ai∈L,n∈N0},

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

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

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

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

A1=⟨Q1,Σ1,δ1,q0,F1⟩

Побудуємо недетермінований автомат A = ⟨Q, Σ, δ, qs, F⟩, для якого виконується:

  • Q = Q1 ∪ {qs}
  • Σ= Σ1
  • F = F1 ∪ {qs}

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

δ(q,a)={δ1(q,a)якщоq∈Q1∧q∉F1δ1(q,a)якщоq∈F1∧a≠ϵδ1(q,a)∪{q0}якщоq∈F1∧a=ϵ{q0}якщоq=qs∧a=ϵ∅якщоq=qs∧a≠ϵ

Приклад

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

Замикання Кліні мови L(A1) — це мова всіх слів, що складаються з пар 00 і 11, наприклад 0000, 110011, 11110000 тощо. Автомат, який допускав би це замикання, побудуємо так: створимо новий початковий стан qs з ε-переходом у колишній початковий стан q0 і додамо ε-переходи зі станів q3 і q4 у стан q0:

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

Джерела

Розділи: Замкненість регулярних мов, Об'єднання регулярних мов, Перетин регулярних мов, Різниця регулярних мов, Доповнення регулярної мови, Конкатенація регулярних мов, Замикання Кліні регулярної мови