Apakah wajib untuk mendefinisikan transisi pada setiap alfabet yang mungkin dalam Deterministic Finite Automata?

Besok adalah presentasi saya dan saya ingin menghapus konsep saya ...

Saya pernah membaca bahwa di DFA, "Untuk setiap negara, transisi pada semua simbol yang mungkin (alfabet) harus ditentukan."

Apakah untuk setiap negara bagian, mendefinisikan transisi pada semua simbol yang mungkin wajib di DFA? Jika tidak, tolong beri contoh?

automata finite-automata nondeterminism HQuser
sumber

Selamat datang di CS.SE! Kami lebih suka bahwa Anda hanya mengajukan satu pertanyaan per posting. Ini terlihat seperti dua pertanyaan terpisah. Akan lebih baik untuk memposting yang kedua (tentang NFA) secara terpisah. Juga, sudahkah Anda mencari secara menyeluruh di situs ini, dan memeriksa definisi formal di buku teks Anda? Jika tidak, Anda harus melakukannya sebelum bertanya; dan Anda harus menunjukkan kepada kami dalam pertanyaan apa yang Anda temukan ketika Anda melakukan itu.

Terima kasih atas sambutan hangatnya, saya benar-benar mencari di situs ini dan juga di google, tetapi saya mendapatkan pandangan yang bertentangan yang sebenarnya membingungkan saya ..

HQuser

Pertanyaan kedua telah dihapus, tetapi Anda dapat menemukannya di riwayat edit dan mempostingnya secara terpisah sebagai pertanyaan terpisah menggunakan tombol 'Ajukan Pertanyaan' di kanan atas. Namun, sebelum bertanya, mohon pastikan untuk melakukan penelitian yang disarankan dan beri tahu kami dalam pertanyaan penelitian apa yang telah Anda lakukan, termasuk memberi tahu kami buku teks mana yang telah Anda baca. Sejauh pertanyaan ini, Anda masih bisa mengedit pertanyaan ini untuk mengatasi umpan balik yang saya berikan di sini dengan mencari definisi formal di buku teks Anda, termasuk dalam pertanyaan, dan menunjukkan interpretasi Anda tentang definisi itu.

Bagaimanapun, ini sepertinya dicakup oleh cs.stackexchange.com/q/12587/755 . Pilihan komunitas, tolong: apakah ini duplikat?

Saya tidak begitu mengerti pertanyaan Anda. Tampaknya menjadi "Saya pernah membaca bahwa definisi adalah X. Apakah definisi X?"

David Richerby

Jawaban:

DFA ditentukan oleh data berikut:

Alfabet . $\Sigma$
Satu set negara . $Q$
Sebuah keadaan awal . $q_0 \in Q$
Satu set akhir menyatakan . $F \subseteq Q$
Sebuah fungsi transisi . $\delta\colon Q \times \Sigma \to Q$

Seperti yang Anda lihat dari tanda tangan , itu menentukan transisi di setiap negara untuk setiap simbol. $\delta$

Yuval Filmus
sumber

Kecuali bahwa DFA kadang-kadang didefinisikan dengan fungsi transisi parsial.

Gilles 'SANGAT berhenti menjadi jahat'

Anda benar, tidak ada definisi "resmi" DFA. Tetapi bacaan OP mengkhianati pengaruh definisi khusus ini.

Yuval Filmus

Harus secara eksplisit mengatakan bahwa fungsi transisi adalah total.

Ryan

Misalkan DFA diizinkan memiliki transisi yang hilang. Apa yang terjadi jika Anda menemukan simbol yang tidak memiliki transisi yang ditetapkan untuknya? Hasilnya tidak terdefinisi. Itu tampaknya akan melanggar karakteristik "deterministik" dari DFA.

Namun, itu sepele untuk mengubah DFA tidak lengkap menjadi DFA lengkap. Cukup tambahkan status baru illegal,, dan petakan transisi yang tidak ditentukan ke illegalstatus. Akhirnya, tambahkan transisi untuk setiap simbol dari illegalnegara kembali ke dirinya sendiri. Ini illegalnegara sering disebut wastafel negara, karena sekali data yang jatuh ke wastafel tidak ada cara untuk keluar.

Jadi, dari perspektif praktis, ini agak diperdebatkan, selama Anda memiliki cara yang jelas untuk menangani transisi yang hilang.

Nathan Davis
sumber

Hati-hati: Transisi yang tidak terdefinisi tidak membuat otomat non-deterministik, hanya tidak lengkap. Ada beberapa definisi DFA yang memungkinkan transisi yang tidak jelas seperti itu karena sepele untuk menyelesaikannya secara sistematis.

Darkhogg

@ Arkhogg, saya tidak harus tidak setuju, tetapi tidak akan determinisme DFA yang tidak lengkap tergantung pada bagaimana implementasi tertentu menangani transisi yang tidak jelas / hilang ini? Dan bukankah implementasi seperti itu secara implisit menyelesaikan DFA?

Nathan Davis

Tidak, itu tidak tergantung pada implementasinya, itu tergantung pada definisi. Jika Anda mendefinisikan DFA sebagai memiliki fungsi transisi total dan kemudian menggunakan fungsi parsial pasti, Anda memiliki perilaku yang tidak ditentukan dan mungkin berakhir dengan non-determinisme, tetapi itu tidak diberikan. Namun, DFA kadang-kadang secara eksplisit didefinisikan untuk menggunakan fungsi parsial, dan ketika menghadapi transisi yang tidak ditentukan perilaku adalah "tidak menerima", titik. Tidak ada non-determinisme atau apa pun yang funky di sana, untuk implementasi apa pun karena hasilnya ditentukan bahkan jika transisi tidak.

Darkhogg

BTW: Anda juga dapat melakukan transformasi sebaliknya. Ambil "otomat total" dan hapus status wastafel untuk mendapatkan "automaton tidak lengkap". Pada akhirnya satu-satunya perbedaan adalah bahwa otomat total selalu dapat membaca kata sampai akhir, dan setelah itu memutuskan apakah ia menerima kata atau tidak, sementara sebagian otomat mampu menolak beberapa kata sebelum membaca semua kata mereka. karakter.

Bakuriu

$\Sigma$ $Q$ $\rho \subseteq Q \times \Sigma \times Q$ $\delta : (Q \times \Sigma) \to 2^Q$ $|\delta(q,\sigma)| \leq 1$ $q\in Q$ $\sigma \in \Sigma$ $\delta(q,\sigma) \neq \emptyset$ $q \in Q$ $\sigma \in \Sigma$

Sebuah kata diterima oleh NFA jika memiliki proses penerimaan. Otomat deterministik memiliki paling banyak satu kali dijalankan. Otomat lengkap memiliki setidaknya satu kali proses.

Beberapa penulis mendefinisikan trim automata sebagai yang di mana masing-masing negara berada di beberapa jalur dari keadaan awal ke keadaan akhir. Untuk bahasa tertentu, Anda tidak dapat memiliki automata yang ramping dan lengkap. Dalam kasus tersebut, akan lebih mudah untuk menjaga persyaratan kelengkapan dari definisi otomat deterministik.

Fabio Somenzi
sumber