Dalam DFA, apakah setiap negara bagian memiliki transisi pada setiap simbol alfabet?

Jika tidak, lalu apa artinya bila untuk beberapa negara dan beberapa simbol a , δ ( q , a ) tidak ada?$q$$a$$\delta(q, a)$

Anda sepertinya menemukan masalah yang kontroversial. Tampaknya para ilmuwan komputer suka berdebat. Saya tentu suka berdebat, jadi begini!

Jawaban saya adalah tegas: Tidak. Automata terbatas deterministik tidak memerlukan transisi dari setiap negara untuk setiap simbol. Arti ketika $\delta(q,a)$ tidak ada hanyalah bahwa DFA tidak menerima string input.

Meskipun Anda dapat membuat definisi DFA yang mensyaratkan bahwa $\delta(q,a)$ memang ada, itu sama sekali bukan kasus bahwa transisi yang hilang membuat struktur yang dihasilkan (apa pun Anda menyebutnya) dengan cara apa pun nondeterministik karena banyak komentator mengklaim. Jika Anda mengambil kursus tentang teori automata maka topik berikutnya adalah bahasa bebas konteks dan automata push-down di mana perbedaan antara automata deterministik dan deterministik bersifat kritis, dan Anda perlu menggunakan definisi non-determinisme yang benar.

Non-determinisme dikaitkan dengan memiliki lebih dari satu transisi hukum.

Saya pikir kita semua setuju dengan definisi Wikipedia berikut (yang akan saya tunjukkan hanya dalam beberapa detik sedikit ambigu):

Otomat terbatas deterministik $M$ adalah 5-tupel, ( $Q$ , $\Sigma$ , $\delta$ , $q_0$ , $F$ ), yang terdiri dari

1. satu set negara terbatas ( $Q$ )
2. seperangkat simbol input terbatas yang disebut alfabet ( $\Sigma$ )
3. fungsi transisi ( $\delta : Q \times \Sigma \rightarrow Q$ )
4. keadaan awal ( $q_0 \in Q)$
5. satu set status terima ( $F \subseteq Q$ ).

Misalkan $w = a_1 a_2 \cdots a_n$ menjadi string di atas alfabet $\Sigma$ . Otomat $M$ menerima string $w$ jika urutan status, $r_0, r_1, \ldots, r_n$ , ada di $Q$ dengan kondisi berikut:

1. $r_0 = q_0$
2. $r_{i+1} = \delta(r_i, a_{i+1})$ , untuk$i = 0, \ldots, n−1$
3. $r_n \in F$ .

Ambiguitas, dan kontroversi mengenai definisi fungsi transisi, $\delta$ (angka "3" dalam daftar berpoin pertama ). Kita semua sepakat bahwa yang membedakan DFA dari NFA adalah bahwa $\delta$ adalah fungsi daripada hubungan . Tetapi $\delta$ suatu fungsi parsial atau total fungsi ?

Definisi DFA berfungsi dengan baik jika $\delta$ adalah fungsi parsial. Diberikan string input, jika Anda mencapai keadaan $q_i$ dengan simbol input $a_j$ mana tidak ada keadaan berikutnya maka automata tidak dapat menerima.

Apalagi ketika Anda memperluas definisi ini untuk membuat definisi automata push-down itu akan menjadi kasus bahwa Anda harus membuat perbedaan bahwa push-down automata dengan fungsi transisi yang fungsi parsial diklasifikasikan sebagai deterministik, bukan deterministik.

Jika fungsi parsial mengganggu Anda maka di sini ada transformasi sepele yang menjadikan $\delta$ fungsi total. (Transformasi ini tidak seperti algoritma konstruksi subset, ia menambahkan paling banyak O (1) menyatakan, linier dalam jumlah asli negara, dan dapat diperluas untuk bekerja dengan PDA. Tidak satu pun dari fakta itu yang benar dari algoritma konstruksi subset .)

1. tambahkan status $q_{\mathrm{error}}$
2. untuk setiap pasangan $(q_i, s_j)$ mana $\delta$ tidak terdefinisi, tentukan $\delta(q_i, s_j) = q_{\mathrm{error}}$ .

Automata ini memiliki $\delta$ yang merupakan fungsi total dan menerima dan menolak set status yang sama persis dengan yang diterima dan ditolak automata asli Anda.

Edit, Januari 2019

Commenter @Alex Smart mengkritik saya karena tidak memberikan referensi, atau untuk menjelaskan mengapa kita harus peduli. Jadi begini:

Alasan kami peduli tentang definisi pasti determinisme vs non-determinisme, adalah bahwa beberapa kelas automata non-deterministik lebih kuat daripada sepupu deterministik mereka, dan beberapa kelas automata non-deterministik tidak lebih kuat daripada sepupu deterministik mereka. Untuk automata terbatas dan mesin Turing, varian deterministik dan non-deterministik memiliki kekuatan yang setara. Untuk pushdown automata ada bahasa di mana perbedaannya penting: Ada NPDA yang menerima bahasa, dan tidak ada DPDA yang menerima bahasa. Untuk automata terbatas linear pertanyaannya adalah (atau terakhir kali saya periksa) terbuka. Peningkatan daya NPDA atas DPDA berasal dari memungkinkan banyak transisi, bukan dari mengubah fungsi transisi dari fungsi total ke fungsi parsial.

Buku-buku dari komunitas kompiler:

Aho dan Ullman, Principles of Compiler Design , 1977: Pertama mendefinisikan NFA (halaman 88) dengan hubungan transisi, lalu (hlm. 90-91):

Kami mengatakan otomat terbatas adalah deterministik jika 1. Tidak memiliki transisi pada input $\epsilon$ . 2. Untuk setiap negara $s$ dan simbol input $a$ , ada paling satu ujung berlabel $a$ meninggalkan $s$ .

Aho, Sethi, dan Ullman, Compiler, prinsip, teknik, dan alat , cetak ulang tahun 1988, serupa, pertama mendefinisikan NFA dengan relasi transisi, kemudian (hlm. 115-116):

Sebuah deterministik finite automata (DFA, untuk pendek) adalah kasus khusus dari finitie robot non-deterministik di mana ... ada paling satu ujung berlabel $a$ meninggalkan $s$ .

(Perhatikan bahwa dalam komentar @Alex Smart, “naga secara khusus menyebutkan bahwa fungsinya total.” Saya berasumsi dia sedang berbicara tentang edisi selanjutnya dengan penulis bersama Lam, yang saat ini tidak saya akses. )

Appel, Implementasi Kompiler Modern di Jawa , 1988 (p. 22):

Dalam deterministic finite automaton (DFA), tidak ada dua sisi yang keluar dari kondisi yang sama dilabeli dengan simbol yang sama.

Appel kemudian menjelaskan bahwa ketika menggunakan DFA untuk mengenali kecocokan terpanjang, kami secara eksplisit menggunakan transisi yang hilang untuk memutuskan kapan harus berhenti (p. 23):

ketika keadaan mati (keadaan nonfinal tanpa transisi keluaran) tercapai, variabel [yang mencatat kecocokan terpanjang yang pernah kita lihat sejauh ini] memberi tahu token apa yang cocok, dan di mana itu berakhir.

Buku-buku dari komunitas switching-theory:

Kohavi, Switching and Finite Automata Theory, 2 / e , 1978, hlm. 611 mengatakan:

Karena diagram keadaan menggambarkan mesin deterministik , transisi keadaan berikutnya harus ditentukan secara unik oleh keadaan saat ini dan simbol input yang dipindai saat ini.

Saya biasanya akan menafsirkan secara unik berarti "tepat satu", bukan "tidak lebih dari satu". (Yaitu, Kohavi tampaknya mengatakan bahwa determinisme membutuhkan fungsi total)

Buku-buku dari komunitas teori komputasi:

Di sini tampaknya lebih umum untuk mendefinisikan DFA sebelum NFA, dan mengharuskan DFA memiliki fungsi transisi total, tetapi kemudian mendefinisikan NPDA sebelum DPDA, dan mendefinisikan "determinisme" sebagai pembatasan hubungan transisi untuk tidak memiliki lebih dari -Satu entri untuk setiap pasangan negara / simbol.

Hal ini berlaku untuk Hopcroft dan Ullman, 1979, Lewis dan Papadimitriou, 1981, dan, terutama Sipser, 2006, yang menggunakan definisi DFA secara pedagogik untuk memperkenalkan definisi formal yang tepat, dan menjelaskan pentingnya mereka dan secara eksplisit mengatakan (hal.36):

$\delta$

$s\times\Sigma$

Menariknya Rabin dan Scott, juga mendefinisikan automata terbatas non-deterministik dalam hal fungsi total! Page 120, Definisi 9:

$M$$S\times\Sigma$$S$

Yaitu: fungsi transisi menjadi total tidak membuat sistem menjadi deterministik!

Sipser 2006 mengikuti Rabin dan Scott dan menggunakan fungsi transisi total dari state / simbol ke power set state untuk definisinya tentang automata terbatas non-deterministik, PDA non-deterministik, dan Mesin Turing non-deterministik, tetapi mengabaikan topik deterministik PDA.

Baik Hopcroft dan Ullman, 1979, dan Lewis dan Papadimitriou, 1981 menggunakan fungsi parsial dalam definisi mereka tentang PDA deterministik. Mereka pertama mendefinisikan NPDA dengan hubungan transisi, dan kemudian ketika mereka sampai ke PDA, Lewis dan Papadimitriou mengatakan (hal. 135),

Automat pushdown adalah deterministik , secara intuitif, jika ada paling banyak satu transisi yang berlaku untuk setiap konfigurasi.

Sementara Hopcroft dan Ullman mengatakan (hlm. 112):

PDA ... bersifat deterministik dalam arti bahwa paling banyak satu gerakan dimungkinkan dari ID apa pun.

$\delta(q,a)$$q \in Q$$a\in \Sigma$$Q$$\Sigma$

$\varepsilon$

Dalam hal komputabilitas, NFA setara dengan DFA - ada algoritma untuk mengkonversi dari NFA ke DFA, dan DFA hanya sepele NFA yang tidak menggunakan nondeterminisme, sehingga mereka berdua menentukan set bahasa reguler.

Ada definisi DFA di sepanjang baris

$A$$|\delta(q,a)| \leq 1$$q$$a$$\delta(q,\varepsilon) \neq \emptyset$$\delta(q,a) = \emptyset$$a \in \Sigma$$A$

Dalam hal ini, Anda tidak memerlukan semua transisi. Jika otomat tidak memiliki transisi yang cocok dengan simbol input berikutnya, ia menolak.

Merupakan latihan yang bagus untuk menunjukkan bahwa kedua definisi tersebut setara dalam hal bahasa mana yang dapat diterima.

Dalam definisi DFA, setiap negara harus memiliki semua alfabet yang dalam £. Sebagai contoh jika £ = {a, b, c} dan Q = {q0, q1, q2}, semua status ini harus memiliki semua simbol a, b, c yang bertransisi ke keadaan lain atau keadaan yang sama.

Jawaban paling sederhana untuk ini adalah, Anda menambahkan status mati untuk simbol kiri . Seperti dalam konversi dari NFA ke DFA, kita mendapatkan Φ transion untuk beberapa simbol, yang menandakan kita membuat status Mati untuk itu.