✖

Перетин регулярних мов

Нехай дано дві регулярні мови 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 регулярна.

Слово належить перетину мов, якщо воно належить і мові L1, і мові L2. Отже, слово має допускати і автомат A1, і автомат A2. Скористаємося точно такою самою ідеєю, як і для об'єднання регулярних мов, лише змінимо множину заключних станів.

Формалізація побудови

Маємо два автомати,

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

Побудуємо автомат A = ⟨Q, Σ, δ, q, F⟩, що допускає мову L(A1) ∩ L(A2). Тут

  • Q = Q1 × Q2
  • Σ= Σ1 ∩ Σ2
  • q = ⟨q0, p0⟩
  • F = F1 × F2

Для функції переходів δ виконується така рівність:

∀q∈Q1,p∈Q2:δ(⟨q,p⟩,a)=⟨δ1(q,a),δ2(p,a)⟩

Приклад

Нехай маємо автомат A1, який допускає всі слова з парною кількістю одиниць:

та автомат A2, який допускає слова з непарною кількістю нулів:

Побудуємо автомат, що допускатиме перетин цих мов. Множина станів цього автомата має вигляд Q = Q1 × Q2, початковий стан — ⟨q0, p0⟩, а заключні стани — F1 × F2:

Далі добудуємо переходи за правилом δ(⟨q,p⟩, a) = ⟨δ1(q, a), δ2(p, a)⟩:

У цьому автоматі, наприклад, зі стану ⟨q0, p0⟩ є перехід на символі 0 у стан ⟨q0,p1⟩. Це означає, що автомат A1 має зі стану q0 перехід на символі 0 назад у стан q0. А автомат A2 на символі 0 переходить зі стану p0 у стан p1.

Автомат можна перевірити. Він має допускати слова на кшталт 110 або 00000 (вони містять парну кількість одиниць і водночас непарну кількість нулів), але не повинен допускати слова на кшталт 11, 111, 1010.

Джерела

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