Konversi ekspresi reguler menjadi otomaton

Kita akan melihat cara mengonversi sembarang ekspresi reguler menjadi otomaton hingga nondeterministik.

Contoh

Sebelum menjelaskan algoritmanya, kita lihat dulu pada contoh apa sebenarnya yang ingin kita capai. Misalkan ada ekspresi reguler berikut: a(b|c)x^∗. Dengan kata-kata, bahasa yang dibangkitkan ekspresi reguler ini dapat digambarkan sebagai string yang diawali huruf “a”, diikuti huruf “b” atau “c”, lalu diikuti huruf “x” sebanyak berapa pun. Dapatkah kita mengonstruksi otomaton yang menerima bahasa ini? Tentu saja, lihat:

Jelas otomaton ini menerima bahasa yang sama. Muncul pertanyaan: apakah untuk setiap ekspresi reguler ada otomaton yang menerima bahasa tersebut? Jawabannya, ya.

Algoritma konversi ekspresi reguler menjadi otomaton

Kita asumsikan inputnya adalah ekspresi reguler R. Dari bagian sebelumnya tentang ekspresi reguler, kita tahu bahwa ekspresi reguler dapat memiliki enam bentuk yang berbeda. Jadi, kita bedakan enam kasus:

1. R = a untuk suatu simbol a ∈ Σ. Artinya, ekspresi reguler hanya berupa satu simbol dari alfabet Σ yang kita gunakan. Otomaton yang menerima satu simbol a terlihat seperti ini:

   

2. R = ϵ, string kosong. Otomaton yang menerima string kosong terlihat seperti ini:

   

3. R = ∅, ekspresi reguler yang membangkitkan bahasa kosong. Otomaton yang mengenali bahasa seperti itu adalah sebagai berikut:

   

4. R = R₁ ∪ R₂, dengan R₁, R₂ ekspresi reguler. Kita sudah tahu bahwa gabungan bahasa reguler juga merupakan bahasa reguler dan bahwa kita dapat menyusun otomaton yang menerima bahasa seperti itu. Dengan kata lain, kita asumsikan bahwa ada otomaton yang mengenali bahasa yang dibangkitkan ekspresi R₁ dan R₂, lalu dengan otomaton-otomaton tersebut kita susun otomaton yang menerima bahasa yang dibangkitkan ekspresi R₁ ∪ R₂. Contoh: jika R₁ = a dan R₂ = ϵ, dengan prosedur tersebut kita memperoleh otomaton berikut:

   

5. R = R₁ ∘ R₂, dengan R₁, R₂ ekspresi reguler. Kasusnya sama seperti pada butir sebelumnya. Konkatenasi bahasa reguler adalah bahasa reguler, sehingga kita dapat menyusun otomaton yang menerima bahasa tersebut. Jadi, jika R₁ = a, R₂ = b, konkatenasinya terlihat seperti ini:

   

6. $R=(R_1^{\ast })$, dengan R₁ ekspresi reguler. Sekali lagi, kita tahu bahwa penutup bahasa reguler adalah bahasa reguler. Jadi, jika R = a^∗, otomatonnya terlihat seperti ini:

   

Dengan menerapkan butir-butir ini secara bertahap, seluruh ekspresi reguler dapat kita konversi menjadi otomaton hingga.

Contoh lengkap

Kita coba mengonversi ekspresi reguler (a|bc)^∗. Secara bertahap, kita memperoleh otomaton-otomaton berikut:

Otomaton yang dihasilkan ini menerima bahasa yang dibangkitkan ekspresi reguler (a|bc)^∗. Tentu saja otomaton ini sangat rumit, dan pasti ada otomaton yang jauh lebih sederhana yang menerima bahasa yang sama. Kita dapat menggunakan algoritma konversi NFA ke DFA, lalu melakukan minimisasi otomaton.

Sumber

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