Bahasa diterima oleh versi modifikasi automata terbatas

Sebuah robot yang terbatas deterministik (DFA) adalah model mesin negara yang mampu menerima semua dan hanya bahasa biasa. DFAs dapat (dan biasanya) didefinisikan sedemikian rupa bahwa setiap negara harus menyediakan beberapa transisi untuk semua elemen dari alfabet masukan; dengan kata lain, fungsi transisi harus (total) fungsi.$\delta : Q \times \Sigma \rightarrow Q$

Bayangkan apa yang akan kita sebut robot yang terbatas ganda deterministik (DDFA). Ini didefinisikan mirip dengan DFA, dengan dua pengecualian: pertama, alih-alih transisi yang mengarah dari satu negara ke negara lain untuk setiap simbol input yang mungkin, itu harus mengarah ke dua negara yang berbeda; kedua, dalam rangka untuk menerima string, semua jalur potensial harus memenuhi salah satu atau yang lain dari kondisi berikut:

1. Semua jalur potensial melalui memimpin DDFA ke sebuah negara menerima (kami akan menyebutnya tipe-1 DDFA).
2. Semua jalur potensial melalui memimpin DDFA negara menerima sama (kita akan menyebutnya tipe-2 DDFA).

Sekarang untuk pertanyaan saya:

Bahasa apa yang diterima oleh DDFA tipe-1 dan tipe-2? Secara khusus, itu kasus yang , L (DDFA) = L (DFA) , atau L (DDFA) \ subsetneq L (DFA) ? Dalam hal L (DDFA) \ neq L (DFA) , apakah ada deskripsi mudah L (DDFA) ?L ( D D F A ) = L ( D F A ) L ( D D F A ) ⊊ L ( D F A ) L ( D D F A ) ≠ L ( D F A ) L ( D D $L(DFA) \subsetneq L(DDFA)$$L(DDFA) = L(DFA)$$L(DDFA) \subsetneq L(DFA)$$L(DDFA) \neq L(DFA)$$L(DDFA)$

Bukti (atau setidaknya cukup fleshed-keluar sketsa) dihargai, jika mereka tidak terlalu rumit.

Ini dikombinasikan dengan jawaban Alex memberikan gambaran lengkap.

$L(DDFA)\subseteq L(DFA)$ dapat dibuktikan dengan mengadaptasi pembangunan Powerset biasa dengan kondisi keadaan akhir dimodifikasi. Dalam pembangunan daya, negara bagian set negara dari otomat asli. Biasanya setelah melakukan pembangunan Powerset, sebuah negara adalah final jika salah satu negara di set adalah final di otomat asli.

• Pada tipe-1 DDFA, negara terakhir dalam robot dibangun adalah set di mana semua elemen bersifat final dalam otomat asli.

• Pada tipe-2 DDFA, negara akhir adalah set tunggal dari negara-negara akhir dari automaton asli.

Dalam kedua kasus, automata yang dihasilkan adalah DFA.

Sekarang ketik-2DDFA hanya dapat mengekspresikan bahasa dan , tergantung pada apakah status awal menerima atau tidak. Hal ini karena dua transisi dari kebutuhan negara untuk pergi ke negara-negara yang berbeda, tetapi penerimaan hanya mungkin jika mereka berakhir di negara yang sama.$\{\epsilon\}$$\emptyset$

Untuk memulai analisis, saya dapat mengatakan bahwa untuk tipe-1.$L(DFA) \subseteq L(DDFA)$

Anda dapat melakukan ini dengan menduplikasi sebuah DFA dan menambahkan tepi ke negara digandakan. Jika keadaan memiliki transisi ke s 2 pada x , Anda membuat transisi dari s 1 ke s ' 2 pada x juga. Selain itu, s ' 1 memiliki transisi ke s 2 dan s ' 2 pada x . Jelas, ini berarti kita akan hampir selalu berada di negara s i dan s ' i pada waktu yang sama (atau mungkin hanya s $s_1$$s_2$$x$$s_1$$s_2'$$x$$s_1'$$s_2$$s_2'$$x$$s_i$$s_i'$$s_i$, Awalnya), dan karenanya kita akan mengenali bahasa yang sama.

Pembaruan: kami juga memiliki untuk tipe-2, karena tidak ada DDFA tipe-2 yang mengenali bahasa { a } . Jika Anda mencoba membuat DDFA seperti itu, Anda memiliki status awal s , dan kemudian Anda harus memiliki dua tepi keluar ke status s 1 dan s 2 pada a , tetapi status ini harus berbeda, dan karenanya dua jalur penerima berakhir di negara-negara menerima yang berbeda.$L(DFA) \neq L(DDFA)$$\{ a \}$$s$$s_1$$s_2$$a$

Bersama-sama dengan jawaban Dave Clarke, yang memberikan Anda analisis lengkap.