Bisakah bahasa memiliki lebih dari satu DFA?

17

Sebagai Contoh ketika kita mempertimbangkan DFA yang memungkinkan string tidak memiliki sub-string 00atau 11saya dapat menghasilkan dua DFA berikut:

masukkan deskripsi gambar di sini

automata finite-automata Madhuri
sumber

Jawaban:

37

Pertama-tama, DFA kiri Anda salah - ia menerima misalnya 011.

Kedua, DFA dapat diminimalkan secara kanonik , jadi dalam hal itu, Anda selalu dapat menemukan satu DFA kanonik untuk bahasa tertentu.

Tetapi secara umum, ada banyak DFA berbeda untuk setiap bahasa, sehingga Anda bisa mendapatkan jawaban yang benar berbeda.

Shaull
sumber
Dan itu bahkan tak terhingga banyaknya hingga isomorfisme.
G. Bach
Untuk menjadi lebih spesifik: itu tak terbatas hingga isomorfisma ketika negara adalah bagian dari satu set tetap, misalnya . Jika kita tidak memperbaikinya, koleksi automata bahkan bukan satu set ... Entah bagaimana saya tidak berpikir ini adalah niat OP :)N
Shaull
Sangat banyak DFA yang berbeda bahkan untuk bahasa yang terbatas?
Bergi
1
@Bergi: Tentu saja - Anda dapat menambahkan sebanyak mungkin status redundan. Ini mungkin terdengar "konyol", dan memang tidak masuk akal ketika Anda membuat robot sendiri. Namun, berkali-kali automata dibangun dengan menerjemahkan dari beberapa formalisme lain (misalnya determinisasi NFA), dalam hal ini Anda sangat mungkin mendapatkan status redundan.
Shaull
@ Samull: Maksud Anda dengan transisi ε atau keadaan yang tidak terjangkau? OK, saya tidak mempertimbangkan itu.
Bergi