Konversi NFA ke DFA

Kita akan melihat cara mengonversi otomaton nondeterministik menjadi otomaton deterministik. Dengan begitu, kita membuktikan bahwa daya komputasi otomaton nondeterministik dan deterministik ekuivalen.

Ide dasar

Misalkan ada otomaton nondeterministik ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ tanpa transisi epsilon. Kita susun otomaton deterministik ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ sedemikian sehingga

• Q_D ⊆ 2^Q_N
• Σ_D = Σ_N
• p₀ = {q₀}
• F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Fungsi transisi δ_D didefinisikan sebagai berikut:

$$\mathrm{\forall }Q\in Q_D,a\in {\mathrm{\Sigma }}_D:{\delta }_D(Q,a)=\bigcup _{q\in Q}{\delta }_N(q,a)$$

Apa artinya? Otomaton nondeterministik dapat berada di beberapa state sekaligus. Misalnya, bisa terjadi bahwa otomaton nondeterministik kita berada di state {q₀, q₁}. Dengan membaca simbol berikutnya, misalnya 1, kita dapat sampai di himpunan state {q₀, q₂, q₃}. Pada versi deterministik dari otomaton yang sama, hal ini tercermin sebagai berikut: kita membuat dua state, menamainya {q₀, q₁} dan {q₀, q₂, q₃}, lalu membuat transisi untuk simbol 1 di antara keduanya. Secara formal, kita berpindah dari satu state ke state lain, tetapi berkat penamaan tersebut kita tahu bahwa pada otomaton nondeterministik kita akan berada di dua state, lalu di tiga state.

Contoh

Misalkan ada otomaton nondeterministik berikut:

Untuk mengonstruksi otomaton deterministik, yang terutama kita perlukan adalah fungsi transisi yang baru. Untuk itu, kita gunakan tabel yang memuat semua transisi. Pada awalnya, tabelnya terlihat seperti ini:

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}\end{array}$$

Pada akhir algoritma, kolom kiri akan memuat semua state otomaton deterministik. Tabel yang sudah terisi kemudian menentukan fungsi transisinya. Sekarang kita tuliskan ke dalam tabel state mana saja yang dapat dicapai jika kita berada di state {q₀} dan inputnya simbol 0 dan 1.

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

Dari state q₀, untuk simbol 0 hanya ada transisi ke state q₁, sedangkan untuk simbol 1 ada transisi ke state q₁ dan q₂. Sekarang kita tambahkan dua state baru ke tabel: {q₁} dan {q₁, q₂}. Mengapa? Setiap kali kita mengisi tabel dengan himpunan state yang belum ada di kolom kiri, himpunan state tersebut kita tambahkan ke kolom kiri.

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}\\ \{q_1,q_2\}\end{array}$$

lalu kita isi lagi. Untuk state {q₁, q₂}, jangan lupa memeriksa kedua state, yaitu gabungan dari state yang dapat dicapai dari q₁ dan state yang dapat dicapai dari q₂.

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\end{array}$$

Kita memperoleh beberapa state baru yang harus ditambahkan ke tabel:

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}\\ \{q_0,q_3\}\end{array}$$

…lalu kita isi lagi transisinya:

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\end{array}$$

State {q₀, q₁, q₃}, {q₁}, dan {q₁,q₂} sudah ada, jadi kita hanya menambahkan state {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{state}/\text{simbol}& 0& 1\\ \left\{q_0\right\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \left\{q_1\right\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_1,q_2\}& \{q_0,q_1,q_3\}& \{q_0,q_3\}\\ \{q_0,q_1,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\\ \{q_0,q_3\}& \left\{q_1\right\}& \{q_1,q_2\}\\ \{q_0,q_1,q_2,q_3\}& \{q_0,q_1,q_3\}& \{q_0,q_1,q_2,q_3\}\end{array}$$

Tidak ada lagi state baru yang ditambahkan, sehingga tabel sudah terisi lengkap. Sekarang tinggal menyusun diagramnya. State otomaton deterministik ada di kolom pertama, sedangkan transisi untuk simbol 0 dan 1 ada di kolom-kolom berikutnya. Setiap state yang memuat suatu state akhir dari otomaton semula juga menjadi state akhir pada otomaton ini. Artinya, setiap state yang memuat q₃ adalah state akhir. Otomatonnya terlihat seperti ini:

Kita dapat menunjukkan bahwa otomaton ini memang bekerja dengan benar. Kita coba menerima string 11001. Pada otomaton deterministik, kita menempuh jalur

$$q_0{\to }^1{q}_1,q_2{\to }^1{q}_0,q_3{\to }^0{q}_1{\to }^0{q}_0,q_1,q_3{\to }^1{q}_0,q_1,q_2,q_3$$

dan otomaton menerima string tersebut, karena state terakhir {q₀, q₁, q₂, q₃} adalah state akhir. Pada otomaton nondeterministik, selama simulasi kita akan sampai di state-state yang sama. Kita mulai dari state q₀, dan untuk simbol 1 kita sampai di state {q₁, q₂}. Simbol 1 berikutnya membawa kita ke state {q₀,q₃}, dan seterusnya untuk state-state berikutnya. Akhirnya, kita berada di semua state {q₀, q₁, q₂, q₃}, dan otomaton menerima string tersebut.

Sumber

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