Penukaran ungkapan nalar kepada automaton

Kita akan melihat cara menukarkan sebarang ungkapan nalar kepada automaton terhingga tak berketentuan.

Contoh

Sebelum menerangkan algoritma itu sendiri, mari kita lihat melalui contoh apa sebenarnya yang ingin kita capai. Katakan kita mempunyai ungkapan nalar berikut: a(b|c)x^∗. Dengan kata-kata, bahasa yang dijana oleh ungkapan nalar ini terdiri daripada rentetan yang bermula dengan huruf “a”, diikuti sama ada oleh huruf “b” atau “c”, dan kemudian oleh sebarang bilangan huruf “x”. Bolehkah kita membina automaton yang menerima bahasa ini? Boleh, lihat:

Jelas bahawa automaton ini menerima bahasa yang sama. Timbul persoalan: adakah bagi setiap ungkapan nalar wujud automaton yang menerima bahasa itu? Ya, wujud.

Penerangan algoritma penukaran ungkapan nalar kepada automaton

Kita andaikan bahawa input ialah ungkapan nalar R. Daripada bahagian sebelum ini tentang ungkapan nalar, kita tahu bahawa ungkapan nalar boleh mempunyai enam bentuk yang berbeza. Oleh itu, kita membezakan enam kes:

1. R = a bagi suatu simbol a ∈ Σ. Maksudnya, ungkapan nalar itu hanya satu simbol daripada abjad Σ yang kita gunakan. Automaton yang menerima satu simbol a kelihatan seperti berikut:

   

2. R = ϵ, iaitu rentetan kosong. Automaton yang menerima rentetan kosong kelihatan seperti berikut:

   

3. R = ∅, iaitu ungkapan nalar yang menjana bahasa kosong. Automaton yang mengenal pasti bahasa sebegini ialah:

   

4. R = R₁ ∪ R₂, dengan R₁, R₂ ialah ungkapan nalar. Kita sudah tahu bahawa kesatuan bahasa nalar juga merupakan bahasa nalar, dan kita boleh membina automaton yang menerima bahasa sebegini. Dengan kata lain, kita menganggap bahawa kita mempunyai automaton yang mengenal pasti bahasa yang dijana oleh ungkapan R₁ dan R₂, dan dengan automaton itu kita membina automaton yang menerima bahasa yang dijana oleh ungkapan R₁ ∪ R₂. Contoh: jika R₁ = a dan R₂ = ϵ, kaedah itu memberikan automaton berikut:

   

5. R = R₁ ∘ R₂, dengan R₁, R₂ ialah ungkapan nalar. Kes ini sama seperti perkara sebelumnya. Perangkaian bahasa nalar ialah bahasa nalar, jadi kita boleh membina automaton yang menerima bahasa sebegini. Jadi, jika R₁ = a, R₂ = b, perangkaiannya kelihatan seperti berikut:

   

6. $R=(R_1^{\ast })$, dengan R₁ ialah ungkapan nalar. Sekali lagi kita tahu bahawa tutupan bahasa nalar ialah bahasa nalar. Jadi, jika R = a^∗, automatonnya kelihatan seperti berikut:

   

Dengan menggunakan perkara-perkara ini satu demi satu, kita menukarkan keseluruhan ungkapan nalar kepada automaton terhingga.

Contoh lengkap

Mari kita cuba menukarkan ungkapan nalar (a|bc)^∗. Kita memperoleh automaton berikut satu demi satu:

Automaton terakhir ini menerima bahasa yang dijana oleh ungkapan nalar (a|bc)^∗. Sudah tentu automaton ini teramat rumit, dan pasti wujud automaton yang jauh lebih mudah yang menerima bahasa yang sama. Kita boleh menggunakan algoritma penukaran NFA kepada DFA dan kemudian melakukan peminimuman automaton.

Sumber

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