Beza bahasa nalar

Katakan kita mempunyai dua bahasa nalar L₁, L₂. Kita akan membuktikan bahawa beza kedua-duanya, L = L₁ ∖ L₂, juga merupakan bahasa nalar.

Idea

Sebenarnya tidak banyak yang perlu dibuktikan. Beza dua set memenuhi hubungan berikut:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

dengan L₂′ ialah pelengkap bahasa L₂. Daripada bab tentang persilangan bahasa nalar dan pelengkap bahasa nalar, kita tahu bahawa bahasa nalar tertutup terhadap kedua-dua operasi ini. Maksudnya, kita boleh membina automaton yang menerima persilangan bahasa dan automaton yang menerima pelengkap bahasa. Oleh itu, automaton ini boleh digunakan untuk membina automaton yang menerima bahasa L₁ ∩ L₂′, dan bahasa ini ialah bahasa L₁ ∖ L₂.

Contoh

Katakan kita mempunyai automaton A₁ berikut, yang menerima semua rentetan yang mengandungi bilangan digit 1 yang genap:

dan automaton A₂, yang menerima rentetan yang mengandungi bilangan digit 0 yang ganjil:

Kita membina automaton yang menerima beza kedua-dua bahasa ini. Untuk itu kita memerlukan automaton A₂′ yang menjadi pelengkap kepada automaton A₂. Kita hanya menukar keadaan akhir dengan keadaan bukan akhir:

Sekarang kita hanya perlu membina automaton A yang menerima persilangan bahasa L(A₁) dan L(A₂′):

Sumber

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