Pelengkap bahasa nalar

Kita mempunyai bahasa nalar L. Kita akan membuktikan bahawa pelengkap bahasa L juga merupakan bahasa nalar.

Apakah pelengkap

Pelengkap bahasa L ialah semua rentetan yang tidak berada dalam bahasa L. Pelengkap ditandakan dengan L'. Maksudnya, bagi abjad Σ:

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

Contohnya, bagi bahasa rentetan yang mengandungi sekurang-kurangnya satu simbol 1, pelengkapnya ialah bahasa yang mengandungi rentetan yang tidak mempunyai sebarang simbol 1.

Kaedah

Kaedahnya sangat mudah. Kita mempunyai bahasa nalar L dan automaton lengkap berketentuan A = ⟨Q, Σ, δ, q₀, F⟩ yang menerimanya (setiap automaton terhingga boleh ditukarkan kepada automaton sebegini). Automaton A' yang menerima L' dibina dengan menukar keadaan akhir dengan keadaan bukan akhir: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Itu sahaja.

Contoh

Katakan kita mempunyai automaton berikut:

Automaton yang menerima pelengkap bahasanya kelihatan seperti berikut:

Sumber

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