Automata keadaan terbatas: keadaan akhir

Dalam kursus konsep bahasa pemrograman kami, instruktur kami mengklaim bahwa tidak apa-apa bagi keadaan akhir untuk mengarah ke keadaan lain dalam diagram keadaan terbatas.

Tetapi ini tampaknya merupakan konsep yang secara fundamental kontradiktif. Karena definisi final adalah definisi yang mengakhiri transisi, yaitu, begitu Anda mencapainya, tidak ada lagi yang bisa dilakukan.

Namun dia menyajikan slide seperti ini, di mana keadaan akhir diwakili oleh dua lingkaran ... Bagaimana mungkin bagi B, D, E, dan H menjadi keadaan akhir ketika mereka jelas tidak?

Anda tampaknya memiliki kesalahpahaman tentang model generatif vs model "mengenali".

Tata bahasa yang Anda miliki di sebelah kanan menghasilkan kata-kata dengan menerapkan aturan, mulai dari variabel awal, dan berhenti setelah tidak ada lagi variabel.

Automata, bagaimanapun, mengenali bahasa sebagai berikut: Anda memberi makan otomat kata, huruf per huruf, dan automaton mengambil transisi berdasarkan huruf yang diberikan kepadanya.

Jika, setelah membaca semua huruf, otomat berakhir dalam keadaan menerima (alias final), maka kita mengatakan bahwa otomat menerima kata.

Jadi lebih baik untuk menganggap mereka sebagai "menerima" negara, daripada "akhir", meskipun kedua istilah tersebut umumnya digunakan.

keadaan final menurut definisi adalah yang mengakhiri transisi, yaitu, begitu Anda mencapainya, tidak ada lagi yang bisa dilakukan.

Sumber kebingungan Anda adalah bahwa ini bukan definisi. "Keadaan akhir" adalah pilihan nama yang buruk, dan sebagian besar penulis tampaknya lebih suka "menerima negara". Definisi adalah bahwa otomat menerima jika dijalankan berakhir dalam keadaan final / menerima dan menolak sebaliknya.

Memang, ini membingungkan! Untuk mengatasi masalah Anda, panggil mereka status "menerima" alih-alih status "final". Karena itulah mereka sebenarnya, hanya sebuah penanda yang memberitahu kita bahwa pada saat ini string yang diproses adalah milik bahasa.

"Status final menurut definisi adalah yang mengakhiri transisi, yaitu, begitu Anda mencapai itu, tidak ada lagi yang bisa dilakukan."

Dalam konvensi tradisional bekerja dengan akseptor (yaitu, state automata terbatas yang memberi tahu Anda apakah string yang diberikan adalah milik / bukan milik bahasa), keadaan akhir adalah yang, ketika dicapai dengan string kosong (inputnya adalah sepenuhnya dikonsumsi) menandakan bahwa string awal diterima, yaitu itu adalah bagian dari bahasa automaton.

Seperti yang Anda lihat. Tata bahasa yang diberikan mengatakan A -> a. Karenanya automatom menerima untuk mengakhiri pada string "a". Tetapi juga memungkinkan A -> aB -> abD -> abc, jadi string "abc" juga diterima. Jika kita menyelesaikan string pada titik ini, kita akan berdiri dalam keadaan akhir sehingga string diterima. Tapi kita mungkin masih ingin senar "ab" diterima. Jadi kita perlu memastikan bahwa {"a", "ab", "abc"} semuanya diterima oleh automaton. Jangan melihat status akhir sebagai kondisi sehingga jika kita memasukinya, kita mungkin tidak akan pernah meninggalkannya, melihatnya sebagai status untuk memberi tahu kita apakah string kita saat ini diterima atau tidak.