✖

Конкатенація регулярних мов

Нехай дано дві регулярні мови L1, L2. Доведемо, що їхня конкатенація L = L1 ∘ L2 також є регулярною мовою.

Що таке конкатенація

Конкатенацією двох слів «010» і «1111» утворюється слово «0101111». Конкатенацію мов утворюємо так: кожне слово з однієї мови з'єднуємо з кожним словом з іншої мови, і виходить нова мова. Конкатенацію двох слів і двох мов позначатимемо кружечком: ∘. Тоді конкатенацію мов L1 і L2 означимо так:

L1∘L2={a∘b|a∈L1,b∈L2}

Ідея доведення

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

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

Побудуємо недетермінований автомат 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. У нашому автоматі можна імітувати обидва способи. Автомат може йти таким шляхом:

q0→0q1→0q1→εp0→0p1→1p2

Цим шляхом автомат спершу «допустить» частину слова 00, а потім частину слова 01. Або він може йти таким шляхом:

q0→0q1→εp0→0p0→0p1→1p2

і тоді автомат спершу «допустить» частину слова 0, а потім частину слова 001. В обох випадках ми, звісно, доходимо до заключного стану p2.

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

Ще раз: маємо дві регулярні мови L1, L2 та два автомати, що допускають ці мови:

A1=⟨Q1,Σ1,δ1,q0,F1⟩A2=⟨Q2,Σ2,δ2,p0,F2⟩

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

  • Q = Q1 ∪ Q2 (водночас припускаємо, що Q1 ∩ Q2 = ∅)
  • Σ= Σ1 ∪ Σ2
  • q = q0
  • F = F2

Функцію переходів δ побудуємо поетапно:

δ(q,a)={δ1(q,a)якщоq∈Q1∧q∉F1δ1(q,a)якщоq∈F1∧a≠εδ1(q,a)∪{p0}якщоq∈F1∧a=εδ2(q,a)якщоq∈Q2

Джерела

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