Сечение на регулярни езици

Нека имаме два регулярни езика L₁, L₂. Ще докажем, че тяхното сечение L = L₁ ∩ L₂ също е регулярен език.

Идея на доказателството

Имаме два регулярни езика L₁ и L₂ и искаме да докажем, че тяхното сечение L₁ ∩ L₂ е отново регулярен език. Тъй като L₁ и L₂ са регулярни езици, съществуват крайни автомати A₁ и A₂, които приемат езиците L₁ и L₂, т.е. L(A₁) = L₁ и L(A₂) = L₂. Ние ще построим краен автомат A, който ще приема езика L₁ ∩ L₂, с което ще докажем, че езикът L₁ ∩ L₂ е регулярен.

Една дума принадлежи на сечението на езиците, ако принадлежи и на езика L₁, и на L₂. Т.е. думата трябва да се приема и от автомата A₁, и от автомата A₂. Ще използваме точно същата идея, каквато използвахме при обединението на регулярни езици, само ще променим множеството на крайните състояния.

Формализация на метода

Имаме два автомата,

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Построяваме автомата A = ⟨Q, Σ, δ, q, F⟩, който приема езика L(A₁) ∩ L(A₂), като

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

За преходната функция δ е в сила следното равенство:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

Пример

Нека имаме този автомат A₁, който приема всички думи, които съдържат четен брой единици:

и автомата A₂, който приема думите, съдържащи нечетен брой нули:

Ще построим автомат, който ще приема сечението на тези езици. Множеството на състоянията на този автомат има вида Q = Q₁ × Q₂, началното състояние е състоянието ⟨q₀, p₀⟩ и крайните състояния са F₁ × F₂:

След това довършваме преходите така, че δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

В този автомат например от състоянието ⟨q₀, p₀⟩ има преход за символа 0 към състоянието ⟨q₀,p₁⟩. Това означава, че автоматът A₁ има от състоянието q₀ преход за символа 0 обратно към състоянието q₀. Автоматът A₂ пък има за символа 0 преход от състоянието p₀ към състоянието p₁.

Автомата можем да изпробваме. Той трябва да приема думи като 110 или 00000 (съдържат четен брой единици и нечетен брой нули), но не трябва да приема думи като 11, 111, 1010.

Източници

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools