Hiệu của hai ngôn ngữ chính quy

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

Ý tưởng

Thực ra không có nhiều điều phải chứng minh. Với hiệu của hai tập hợp, ta có hệ thức sau:

$$L_1\setminus L_2=L_1\cap \overline{L_2},$$

trong đó $\overline{L_2}$ là phần bù của ngôn ngữ L₂. Từ các bài về giao của hai ngôn ngữ chính quy và phần bù của ngôn ngữ chính quy, ta biết rằng lớp ngôn ngữ chính quy đóng đối với cả hai phép toán này. Nghĩa là ta có thể xây dựng ôtômat đoán nhận giao của hai ngôn ngữ và ôtômat đoán nhận phần bù của một ngôn ngữ. Dùng các ôtômat này, ta xây dựng được ôtômat đoán nhận ngôn ngữ $L_1\cap \overline{L_2}$, mà đó cũng chính là ngôn ngữ L₁ ∖ L₂.

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 hiệu của hai ngôn ngữ này. Trước hết cần ôtômat A₂′ đoán nhận phần bù của ngôn ngữ do A₂ đoán nhận. Chỉ cần đổi trạng thái kết thúc thành không kết thúc và ngược lại:

Bây giờ chỉ còn xây dựng ôtômat A đoán nhận giao của hai ngôn ngữ L(A₁) và L(A₂′):

Tài liệu tham khảo

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