Phần bù của ngôn ngữ chính quy

Cho ngôn ngữ chính quy L. Ta sẽ chứng minh phần bù của ngôn ngữ L cũng là ngôn ngữ chính quy.

Phần bù là gì

Phần bù của ngôn ngữ L gồm mọi xâu không thuộc ngôn ngữ L. Phần bù kí hiệu là $\bar{L}$. Tức là với bảng chữ cái Σ, ta có:

$$\bar{L}=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

Chẳng hạn, phần bù của ngôn ngữ gồm các xâu chứa ít nhất một kí hiệu 1 là ngôn ngữ gồm các xâu không chứa kí hiệu 1 nào.

Cách làm

Cách làm rất đơn giản. Cho ngôn ngữ chính quy L và ôtômat đơn định đầy đủ A = ⟨Q, Σ, δ, q₀, F⟩ đoán nhận ngôn ngữ đó (mọi ôtômat hữu hạn đều chuyển được thành ôtômat như vậy). Để xây dựng ôtômat A' đoán nhận $\bar{L}$, ta đổi trạng thái kết thúc thành không kết thúc và ngược lại: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Thế là xong.

Ví dụ

Cho ôtômat sau:

Ôtômat đoán nhận phần bù của ngôn ngữ này như sau:

Tài liệu tham khảo

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