Komplemen bahasa reguler

Misalkan ada bahasa reguler L. Kita akan membuktikan bahwa komplemen bahasa L juga merupakan bahasa reguler.

Apa itu komplemen

Komplemen bahasa L adalah semua string yang tidak termasuk bahasa L. Komplemen dilambangkan dengan L^c. Jadi, untuk alfabet Σ berlaku:

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

Misalnya, untuk bahasa string yang memuat setidaknya satu simbol 1, komplemennya adalah bahasa yang memuat string-string tanpa satu pun simbol 1.

Prosedur

Prosedurnya sangat sederhana. Ada bahasa reguler L dan otomaton lengkap deterministik A = ⟨Q, Σ, δ, q₀, F⟩ yang menerimanya (setiap otomaton hingga dapat diubah menjadi otomaton seperti itu). Otomaton A' yang menerima L^c dikonstruksi dengan menukar state akhir dan state bukan akhir: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Selesai.

Contoh

Misalkan ada otomaton berikut:

Otomaton yang menerima komplemen bahasanya terlihat seperti ini:

Sumber

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