Bagaimana NFA menggunakan transisi epsilon?

Pada gambar di bawah, saya mencoba mencari tahu apa sebenarnya yang diterima NFA ini.

Yang membingungkan saya adalah jump at .q $\epsilon$$q_0$

• Jika dimasukkan, apakah sistem pindah ke dan (status terima)?q 0 q $0$$q_0$ $q_1$

• Jika dimasukkan, apakah sistem pindah ke dan ?q 1 q $1$$q_1$$q_2$

• Apakah sistem hanya pindah ke (kondisi terima), jika tidak ada input yang diberikan (string kosong)?$q_1$

Setiap kali Anda berada dalam keadaan yang memiliki transisi , itu berarti Anda secara otomatis berada di KEDUA status, untuk menyederhanakan ini kepada Anda:$\epsilon$

Jika string adalah maka automata Anda berakhir dengan danq 0 q $\epsilon$$q_0$$q_1$

Jika string Anda '0' itu akan menjadi lagi di danq $q_0$$q_1$

Jika string Anda adalah '1', itu hanya akan berada di , karena jika Anda melihat dari titik , Anda memiliki transisi '1' ke , tetapi Anda juga harus melihat jika Anda berada di ( jika Anda berada di Anda selalu berada di juga) maka tidak ada transisi '1', jadi jalur alternatif ini hanya "mati".q 0 q 2 q 1 q 0 q $q_2$$q_0$$q_2$$q_1$$q_0$$q_1$

Hanya dengan melihat kasus-kasus ini, mudah untuk melihat bahwa automata Anda menerima , , dan dari ke , satu-satunya cara untuk mencapai adalah , jadi, ini melanjutkan automata Anda ke , ,0 ∗ q 0 q 1 q 2 0 ∗ 11 ∗ 1 ϵ 0 ∗ 0 ∗ 11 ∗$\epsilon$$0^*$$q_0$$q_1$$q_2$$0^*11^*1$$\epsilon$$0^*$$0^*11^*1$

Semoga ini bisa membantu Anda, jika Anda memiliki keraguan lebih lanjut, tanyakan saja!

Dalam status tanpa membaca input apa pun, NFA tetap berada di dan (dalam semesta alternatif, jika Anda mau) , NFA juga bergerak ke status . Ini mirip dengan apa yang akan terjadi dalam NFA yang memiliki dua transisi ke status berbeda pada input karakter. Secara khusus, NFA Anda menerima string kosong, karena tanpa input, NFA Anda dapat beralih ke status penerimaan .$q_0$$q_0$$q_1$$q_1$

Melanjutkan contoh Anda, dari keadaan melihat input , itu akan mengkonsumsi simbol itu, tetap dalam status (loop) dan juga pergi ke menyatakan , dengan demikian menerima input . Dalam status membaca input , NFA akan masuk ke status . Mungkin juga tidak mengkonsumsi , mengubah ke status di alam semesta lain dan terjebak di sana (dan tidak menerima, karena tidak membaca semua input), karena tidak ada transisi dari pada .$q_0$$0$$q_0$$q_1$$0$$q_0$$1$$q_2$$1$$q_1$$q_1$$1$

Lihat apakah Anda dapat meyakinkan diri sendiri bahwa bahasa yang diterima oleh mesin ini dilambangkan dengan ekspresi reguler , yaitu string apa pun yang terdiri dari nol atau lebih s diikuti oleh tidak ada sama sekali atau dua atau lebih s.$0^*+0^*11^*1$$0$$1$

Ngomong-ngomong, ada sebuah algoritma yang mengambil NFA dengan -moves dan menghasilkan NFA yang setara tanpa -moves, yang saya harapkan akan Anda pelajari segera.$\epsilon$$\epsilon$

Saya mencoba membangun DFA untuk NFA ini

$\sum$ - set alfabet

$Q$Status- diatur

$\sigma(Q\times (\sum \cup {\epsilon} )) \to P(Q)$ status func

$q_0 = q_0$

$F \subseteq Q, F = \{q_0\}$

Karena setiap NFA memiliki DFA yang sama mari kita buat DFA untuk NFA yang diberikan ini.$M'$

alfabet - sama

$Q' = P(Q)$ - menyatakan

Keadaan saat ini adalah$R \in P(Q)$

$E(R)$ - set pengembalian pengembalian epsilon dari keadaan yang dapat dicapai lebih dari nol atau lebih - koneksi untuk setiap$\epsilon$$r \in R$

$\sigma'(R,a) = \bigcup_{r \in R} E(\sigma(r,a))$ -transisi

$q'_{0} = E(\{q_0\})$

$F' = P(Q) \div F$

Beberapa menghitung FSM ini

$1.$ $\epsilon$ pada input: keadaan awal termasuk sehingga FSM menerima$q'_{0} = E(\{q0\}) = \{q_0, q_1\}$$q_1$$\epsilon$

$2.$ $0*$ pada input: jadi FSM menerima$\sigma'(\{q_0, q_1\}, 0) = E(\sigma(q_0,0)) \cup E(\sigma(q_1,0)) = \{q_0, q_1\} \cup \{ \} = \{q_0, q_1\}$$0*$

setidaknya$\{\epsilon, 0* \} \subset L (M')$

Terima kasih kepada David Richerby