✖

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

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

Нехай дано дві регулярні мови 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. Скористаємося точно такою самою ідеєю, як і для об'єднання регулярних мов, лише змінимо множину заключних станів.

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

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

\begin{eqnarray} A_1&=&\left<Q_1, \Sigma_1, \delta_1, q_0, F_1\right>\\ A_2&=&\left<Q_2, \Sigma_2, \delta_2, p_0, F_2\right> \end{eqnarray}

Побудуємо автомат $A=\left<Q, \Sigma, \delta, q, F\right>$, що допускає мову L(A1)∩ L(A2). Тут

  • Q = Q1 × Q2
  • $\Sigma = \Sigma_1 \cap \Sigma_2$
  • q = <q0, p0>
  • F = F1 × F2

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

$$ \forall q\in Q_1, p\in Q_2: \delta(\left<q,p\right>, a) = \left<\delta_1(q, a), \delta_2(p, a)\right> $$

Приклад

Нехай маємо автомат 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.

Джерела