Selisih bahasa reguler

Misalkan ada dua bahasa reguler L₁, L₂. Kita akan membuktikan bahwa selisih keduanya, L = L₁ ∖ L₂, juga merupakan bahasa reguler.

Ide

Sebenarnya tidak banyak yang perlu dibuktikan. Untuk selisih dua himpunan berlaku hubungan berikut:

$$L_1\setminus L_2=L_1\cap L_2^c,$$

dengan $L_2^c$ komplemen bahasa L₂. Dari bab tentang irisan bahasa reguler dan komplemen bahasa reguler, kita tahu bahwa bahasa reguler tertutup terhadap kedua operasi ini. Artinya, kita dapat mengonstruksi otomaton yang menerima irisan bahasa dan otomaton yang menerima komplemen bahasa. Otomaton-otomaton ini dapat kita gunakan untuk mengonstruksi otomaton yang menerima bahasa $L_1\cap L_2^c$, yang tidak lain adalah bahasa L₁ ∖ L₂.

Contoh

Misalkan ada otomaton A₁ berikut, yang menerima semua string dengan banyak angka 1 genap:

dan otomaton A₂, yang menerima string dengan banyak angka 0 ganjil:

Kita konstruksi otomaton yang menerima selisih kedua bahasa ini. Untuk itu, kita perlu otomaton A₂′ yang merupakan komplemen otomaton A₂. Kita cukup menukar state akhir dan state bukan akhir:

Sekarang tinggal mengonstruksi otomaton A yang menerima irisan bahasa L(A₁) dan L(A₂′):

Sumber

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