Kondisi untuk infinitude dari bahasa robot kondisi terbatas

9

Ada teorema yang mengatakan bahwa:

Diberi otomat keadaan terbatas yang memiliki keadaan, jika ada string yang panjangnya memenuhi n \ leq | w | \ leq 2n-1 maka bahasa yang diterima oleh automaton tidak terbatas.w n ≤ | w | ≤ 2 n - 1nwn≤|w|≤2n−1

Saya mengerti kendala |w|≥n , tapi saya tidak mengerti mengapa kendala |w|≤2n−1 ada di sana.

automata finite-automata rahul sharma
sumber

Jawaban:

5

Dalam skenario terburuk, NFA Anda dapat terlihat seperti ini:

W terkecil wyang dijamin loop (memaksa untuk menerima bahasa tak terbatas) memiliki ukuran 2n−1 .

André Souza Lemos
sumber
Ketika saya mulai dari q0 dan setelah itu ketika saya kembali pada q0, itu berarti ada siklus di mesin. Bukankah itu hal yang cukup dalam kasus terburuk, mengapa kita kembali ke tahap akhir lagi dalam kasus ini? Sejauh yang saya mengerti dari gambar ini, bahwa kita akan memompa loop ini sekali dan kemudian pergi ke tahap akhir lagi, jadi itu berarti sekali kita masuk pada tahap akhir maka kita mengasumsikan bahwa ini bukan string saya karena kembali ke keadaan lain, tetapi begitu kembali ke tahap akhir lagi, maka kami yakin bahwa ini string kami karena ada beberapa loop yang memiliki dipompa?
rahul sharma
Kami mencoba untuk membuktikan sesuatu tentang robot, yaitu, bahwa ia menerima bahasa yang tak terbatas. Dalam cara bukti diformulasikan, string adalah dugaan, yang ukurannya diasumsikan berada dalam interval tertentu. Jelas, jika automaton memiliki loop, maka string ada. Apa yang terjadi adalah bahwa jika tidak mungkin ditemukan di dalam interval ini, maka mesin tidak bisa seperti yang ada dalam gambar. Entah itu tidak memiliki loop, atau tidak memiliki status akhir. w bwww
André Souza Lemos
Saya mengerti maksud Anda. Saya hanya mencoba memahami batas atas pada interval, mengapa 2n-1 dan mengapa tidak 2n-x (x dapat berupa apa pun kecuali 1) .Dalam gambar di atas dapat kita katakan loop adalah qo -q1 .... qn-q1 .... qn, benar (maks. loop)? Tapi ketika saya q0 lagi (q0 ... aq, q0), bukankah itu berarti ada loop, jadi maksimum harus n, mengapa kita menambahkan n-1 ke n (atau mengapa kita akan ke keadaan akhir lagi). Saya mengalami kesulitan dalam mendapatkan ini :(. dapat maks. loop menjadi q0., q1, q2 ..qn, qn-1, qn-1..q0, sesuatu seperti itu?
rahul sharma
Batas atas adalah karena tidak lebih buruk dari itu. lebih kecil dari , dan saya baru saja menunjukkan kepada Anda sebuah otomat yang membutuhkan langkah . Tidak ada yang membutuhkan lebih banyak (dan melakukan pekerjaan), tetapi ada satu yang membutuhkan jumlah ini. 2 n - x 2 n - 1 2 n - 12n−12n−x2n−12n−1
André Souza Lemos
Sudah sekarang. Hanya satu keraguan kecil. Asumsikan saya memiliki 4 status di mesin saya. Dan saya membaca string abc dan saya mencapai status akhir dan kemudian saya membaca d di sana dan kembali ke keadaan awal, dan kemudian pergi ke keadaan akhir lagi, jadi string saya akan menjadi abcdabc. Bagaimana saya bisa memecah ini menjadi memompa lemma, dan mendapatkan y ^ i, di mana i = 1, untuk menunjukkan bahwa y telah dipompa sekali.?
rahul sharma
5

Kondisi tambahan memungkinkan Anda menulis algoritma garis lurus - periksa semua string dengan panjang dalam interval ini - untuk menentukan (dalam) keterbatasan bahasa yang diterima. Dengan demikian, Anda mendapatkan bukti bahwa properti ini dapat dipilih (yang bukan untuk sebagian besar model automata dengan daya super-reguler).

Raphael
sumber
3

Teorema lengkap menyatakan kesetaraan daripada implikasi :

Bahasa yang diterima oleh status NFA tidak terbatas jika dan hanya jika mengandung kata yang ukurannya memenuhi .w n ≤ | w | ≤ 2 n - 1nwn≤|w|≤2n−1

Kondisi ekstra dengan demikian membuat teorema lebih kuat .|w|≤2n−1

Yuval Filmus
sumber