Giao của hai ngôn ngữ chính quy

Cho hai ngôn ngữ chính quy L₁, L₂. Ta sẽ chứng minh giao của chúng L = L₁ ∩ L₂ cũng là ngôn ngữ chính quy.

Ý tưởng chứng minh

Cho hai ngôn ngữ chính quy L₁ và L₂, ta muốn chứng minh giao L₁ ∩ L₂ của chúng cũng là ngôn ngữ chính quy. Vì L₁ và L₂ là ngôn ngữ chính quy nên tồn tại các ôtômat hữu hạn A₁ và A₂ đoán nhận các ngôn ngữ L₁ và L₂, tức là L(A₁) = L₁ và L(A₂) = L₂. Ta sẽ xây dựng ôtômat hữu hạn A đoán nhận ngôn ngữ L₁ ∩ L₂, qua đó chứng minh ngôn ngữ L₁ ∩ L₂ là chính quy.

Một xâu thuộc giao của hai ngôn ngữ nếu nó thuộc ngôn ngữ L₁ và đồng thời thuộc L₂. Tức là xâu phải được cả ôtômat A₁ lẫn ôtômat A₂ đoán nhận. Ta dùng đúng ý tưởng đã dùng cho hợp của hai ngôn ngữ chính quy, chỉ thay đổi tập các trạng thái kết thúc.

Hình thức hoá cách làm

Cho hai ôtômat

$$\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}$$

Ta xây dựng ôtômat A = ⟨Q, Σ, δ, q, F⟩ đoán nhận ngôn ngữ L(A₁) ∩ L(A₂), trong đó

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

Hàm chuyển trạng thái δ thoả mãn hệ thức sau:

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

Ví dụ

Cho ôtômat A₁ đoán nhận mọi xâu chứa một số chẵn chữ số 1:

và ôtômat A₂ đoán nhận các xâu chứa một số lẻ chữ số 0:

Ta xây dựng ôtômat đoán nhận giao của hai ngôn ngữ này. Tập trạng thái của ôtômat này có dạng Q = Q₁ × Q₂, trạng thái bắt đầu là ⟨q₀, p₀⟩ và các trạng thái kết thúc là F₁ × F₂:

Tiếp theo ta bổ sung các phép chuyển sao cho δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

Chẳng hạn, trong ôtômat này có phép chuyển từ trạng thái ⟨q₀, p₀⟩ ứng với kí hiệu 0 đến trạng thái ⟨q₀,p₁⟩. Điều đó có nghĩa là ở ôtômat A₁, từ trạng thái q₀ có phép chuyển ứng với kí hiệu 0 quay lại trạng thái q₀, còn ở ôtômat A₂, ứng với kí hiệu 0 có phép chuyển từ trạng thái p₀ đến trạng thái p₁.

Ta có thể thử ôtômat này. Ôtômat phải đoán nhận các xâu như 110 hay 00000 (chứa một số chẵn chữ số 1 và đồng thời một số lẻ chữ số 0), nhưng không đoán nhận các xâu như 11, 111, 1010.

Tài liệu tham khảo

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