Penukaran NFA kepada DFA

Kita akan melihat cara menukarkan automaton tak berketentuan (NFA) kepada automaton berketentuan (DFA). Dengan cara ini kita membuktikan bahawa kuasa pengiraan automaton tak berketentuan dan automaton berketentuan sama.

Idea asas

Katakan kita mempunyai automaton tak berketentuan ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ tanpa peralihan epsilon. Kita membina automaton berketentuan ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ dengan

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

Fungsi peralihan δ_D ditakrifkan seperti berikut:

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

Apakah maksudnya? Automaton tak berketentuan boleh berada dalam beberapa keadaan serentak, jadi kita mungkin sampai ke situasi apabila automaton tak berketentuan kita berada dalam keadaan {q₀, q₁}. Selepas membaca simbol seterusnya, misalnya 1, kita mungkin sampai ke set keadaan {q₀, q₂, q₃}. Dalam versi berketentuan bagi automaton yang sama, hal ini diwakili dengan membina dua keadaan, menamakannya {q₀, q₁} dan {q₀, q₂, q₃}, dan menambahkan peralihan bagi simbol 1 di antara kedua-duanya. Secara formal kita beralih dari satu keadaan ke satu keadaan lain, tetapi berkat nama itu kita tahu bahawa dalam automaton tak berketentuan kita akan berada dalam dua dan tiga keadaan masing-masing.

Contoh

Katakan kita mempunyai automaton tak berketentuan berikut:

Untuk membina automaton berketentuan, perkara utama ialah membina fungsi peralihan baharu. Kita dibantu oleh jadual yang mencatat semua peralihan. Pada mulanya jadual kelihatan seperti berikut:

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

Pada akhir algoritma, lajur kiri akan mengandungi semua keadaan automaton berketentuan. Jadual yang lengkap pula menentukan fungsi peralihan. Sekarang kita mencatat dalam jadual keadaan yang dicapai jika kita berada dalam keadaan {q₀} dan input ialah simbol 0 dan 1.

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

Dari keadaan q₀, bagi simbol 0 terdapat peralihan ke keadaan q₁ sahaja, manakala bagi simbol 1 terdapat peralihan ke keadaan q₁ dan q₂. Sekarang kita menambahkan dua keadaan baharu ke dalam jadual: {q₁} dan {q₁, q₂}. Mengapa? Setiap kali kita mencatat dalam jadual suatu set keadaan yang belum ada dalam lajur kiri, kita menambahkan set keadaan itu ke lajur kiri.

$$\begin{array}{ccc}\text{keadaan}/\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}$$

dan kita isi jadual sekali lagi. Bagi keadaan {q₁, q₂}, jangan lupa menyemak kedua-dua keadaan, iaitu kesatuan antara keadaan yang dicapai dari q₁ dengan keadaan yang dicapai dari q₂.

$$\begin{array}{ccc}\text{keadaan}/\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 keadaan baharu yang perlu ditambahkan ke dalam jadual:

$$\begin{array}{ccc}\text{keadaan}/\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}$$

…dan kita lengkapkan peralihan sekali lagi:

$$\begin{array}{ccc}\text{keadaan}/\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}$$

Keadaan {q₀, q₁, q₃}, {q₁} dan {q₁,q₂} sudah ada dalam jadual, jadi kita hanya menambahkan keadaan {q₀,q₁,q₂,q₃}.

$$\begin{array}{ccc}\text{keadaan}/\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}$$

Tiada keadaan baharu yang ditambahkan, jadi jadual sudah lengkap. Sekarang kita hanya perlu melukis gambar rajah. Keadaan automaton berketentuan berada dalam lajur pertama, manakala peralihan bagi simbol 0 dan 1 berada dalam lajur yang lain. Setiap keadaan yang mengandungi suatu keadaan akhir daripada automaton asal juga menjadi keadaan akhir dalam automaton ini. Maksudnya, setiap keadaan yang mengandungi q₃ ialah keadaan akhir. Automaton itu kelihatan seperti berikut:

Kita boleh menunjukkan bahawa automaton ini benar-benar berfungsi dengan betul. Mari kita cuba menerima rentetan 11001. Dalam automaton berketentuan, kita mengikut laluan

$$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 automaton akan menerima rentetan itu kerana keadaan terakhir {q₀, q₁, q₂, q₃} ialah keadaan akhir. Dalam automaton tak berketentuan, semasa simulasi kita akan sampai ke keadaan yang sama: kita bermula pada keadaan q₀, dan bagi simbol 1 kita sampai ke keadaan {q₁, q₂}. Simbol 1 yang seterusnya membawa kita ke keadaan {q₀,q₃}, dan begitulah seterusnya. Akhirnya kita berada dalam semua keadaan {q₀, q₁, q₂, q₃} dan automaton menerima rentetan itu.

Sumber

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