Bahasa reguler tidak diterima oleh DFA memiliki paling banyak tiga negara

Jelaskan bahasa reguler yang tidak dapat diterima oleh DFA yang hanya memiliki tiga negara.

Saya tidak begitu yakin harus mulai dari mana dan bertanya-tanya apakah ada yang bisa memberi saya beberapa tips atau saran. Saya mengerti bahwa lemma pemompaan dapat digunakan untuk membuktikan bahwa suatu bahasa tidak teratur, tetapi dalam hal ini, itu harus merupakan bahasa biasa. Jika ada yang punya pikiran itu akan dihargai.

Lemma pemompaan dapat dinyatakan untuk memperhitungkan jumlah status dalam DFA. Setiap bahasa diterima oleh DFA dengan status memenuhi lemma pemompaan berikut:$L$$p$

Setiap kata dengan panjang setidaknya dapat dipecah sebagai , di mana dan , sehingga untuk semua .p w = x y z | x y | ≤ p | y | ≥ 1 x y i z ∈ L i ≥ $w$$p$$w=xyz$$|xy| \leq p$$|y| \geq 1$$xy^iz \in L$$i \geq 0$

Anda dapat menggunakan karakterisasi ini untuk membuktikan bahwa bahasa membutuhkan status .p + $\{0^p\}$$p+1$

Metode lain adalah dengan menggunakan teorema Myhill - Nerode. Dua kata adalah inequivalent (sehubungan dengan beberapa bahasa ) jika untuk beberapa kata , baik dan atau sebaliknya. Teorema Myhill - Nerode menyatakan bahwa jika ada kata berpasangan yang tidak berpasangan, maka setiap DFA untuk memiliki setidaknya status. Sebagai contoh , Anda dapat menemukan kata-kata yang tidak setara berpasangan, yaitu .$x,y$$L$$z$$xz \in L$$yz \notin L$$p$$L$$p$$L = \{0^p\}$$p+1$$\epsilon,0,\ldots,0^p$

Jawaban Yuval sangat bagus. Formulasi yang lebih sederhana dari apa yang dia gambarkan adalah bahwa automata terbatas tidak dapat menghitung tinggi secara sewenang-wenang, dan jumlah yang dapat mereka hitung dibatasi oleh status angka dalam automata. Lebih tepatnya, untuk automata untuk menghitung ke , perlu negara (satu negara akan ).$p$$p+1$$0$

Ini, pada dasarnya, adalah seluruh ide di balik lemma pemompaan: jika sebuah string sangat panjang, automata yang terbatas harus "lupa" seberapa tinggi dihitung dan mulai dari awal lagi, memungkinkan Anda untuk mengulangi bagian berulang tanpa peduli. .

Oleh karena itu, bahasa reguler apa pun yang memerlukan penghitungan hingga 3 untuk memvalidasi kata di dalamnya, tidak dapat dijelaskan oleh automata hingga ukuran 3.

Bisakah Anda memikirkan bahasa seperti itu? (Profesor Anda mungkin juga mengharapkan Anda untuk membuktikan argumen penghitungan ini, meskipun dalam kurikulum saya pemahaman ini tentang lemma pemompaan diterima begitu saja)

Ada algoritma untuk meminimalkan DFA. Pilih saja bahasa yang memiliki DFA minimal 4 (atau lebih) negara. Apa pun yang memiliki panjang minimal 3 simbol akan dilakukan, yaitu bahasa ekspresi reguler , atau (bahkan lebih sederhana) . Untuk mengetahui alasannya, intip bukti lemma pemompaan untuk bahasa reguler.$a^3 a^*$$a^3$

ide lain, diagonalisasi ! sebutkan semua DFA 3-atau-lebih sedikit, ambil gabungan dari semuanya, dan kemudian ambil komplemen. ini adalah DFA dengan penutupan operasi bahasa biasa. ini dapat dibangun melalui algoritma, tetapi pertanyaannya hanya meminta deskripsi .