Apakah

Saya mengambil ujian teori perhitungan saya beberapa minggu yang lalu, dan ini adalah salah satu pertanyaan:

Asumsikan bahasa $L=\{(a^nb^m)^r \mid n,m,r\ge 0\}$

Apakah L teratur? Jika ya, berikan ekspresi reguler atau otomat untuk itu.

Setelah saya bertanya secara singkat kepadanya jawaban setelah ujian, tampaknya itu benar-benar biasa (saya percaya dia mengatakan ungkapan itu sederhana ). Namun sepertinya saya tidak mengerti mengapa itu terjadi. Cara saya melihatnya, yang concatenating r kali, seperti ini: $(a^*b^*)^*$ $a^nb^m$

, $a^nb^ma^nb^ma^nb^m...a^nb^ma^nb^m$

yang tidak teratur karena tidak ada cara bagi robot untuk mengingat n dan m setiap waktu. Di mana saya salah di sini?

EDIT: Saya berbicara dengan profesor lagi, dia mengakui itu adalah kesalahan. Bahasanya memang tidak teratur.

formal-languages regular-languages regular-expressions Exci
sumber

Anda harus bertanya kepada guru Anda apakah bahasa

sama dengan bahasa

L

$L$

K = {a^{n_{1}} b^{m_{1}} a^{n_{2}} b^{m_{2}} \dots a^{n_{r}} b^{n_{r}} ∣ r \geq 0, a_{1}, \dots, a_{r} \geq 0, b_{1}, \dots, b_{r} \geq 0}

$K = \lbrace a^{n_1} b^{m_1} a^{n_2} b^{m_2} \cdots a^{n_r} b^{n_r} \mid r \geq 0, a_1, \ldots, a_r \geq 0, b_1, \ldots, b_r \geq 0\rbrace$ . Jika dia mengatakan "ya" maka katakan padanya aku bilang padamu pertanyaannya buruk.

Andrej Bauer

Yang tampaknya satu-satunya cara bisa teratur, dan sebenarnya ini adalah apa yang saya awalnya buru-buru berpikir dan benar-benar dianggap (a b ) *, tapi kemudian terhapus itu mewujudkan n dan m tinggal sama (atau harus ..), dan memberikan ketidaksepakatan memompa lemma untuk r = 2, mengatakan hal yang sama diterapkan untuk r yang lebih besar (mungkin bukan solusi yang lengkap baik tetapi tampaknya berada di arah yang benar). Tak perlu dikatakan, saya mendapat 0 untuk pertanyaan itu. Saya akan mencoba menghubunginya.

Saya pasti akan mengerti pertanyaan seperti yang Anda lakukan pada awalnya.

Andrej Bauer

Lihat di sini untuk lebih banyak cara untuk menunjukkan bahwa suatu bahasa tidak teratur.

Raphael

Anda juga bisa membuktikan hal yang sama dengan bantuan memompa lemma

SAHIL THUKRAL

Jawaban:

Bahasa tidak teratur, karena dapat dibuktikan menggunakan metode Nerode. Pertimbangkan kata-kata berikut untuk . Kemudian , tapi untuk , . Oleh karena itu setiap robot untuk harus dalam keadaan yang berbeda setelah membaca setiap , yang bertentangan finiteness nya. $L$ $w_n = a^n b$ $n \in \mathbb{N}$ $w_n^2 \in L$ $n \neq m$ $w_n w_m \notin L$ $L$ $w_n$

Yuval Filmus
sumber

Dalam komentar Anda, Anda memberi petunjuk bahwa Anda (kutipan) "memberikan penolakan lemma pemompaan untuk , mengatakan hal yang sama berlaku untuk lebih besar ". $r=2$ $r$

$L$ $L\cap a^*ba^*b = \{ a^n b a^n b \mid n\ge 0\}$ $r=2$ $m=1$

Hendrik Jan
sumber

L

$L$

L^{'} \supset L

$L' \supset L$

L \cap R

$L\cap R$

L

$L$

R

$R$

Tentu saja. Saya khawatir bahwa siswa akan membaca "pengaturan yang efektif ..." dan menerapkannya tanpa menggunakan properti penutupan.

Raphael

Bahasa: {(a ⁿ b ^m ) ^r | n, m, r≥0} adalah tidak biasa, karena sementara otomat / mesin membaca urutan pertama huruf 'a' dan kemudian huruf 'b', perlu untuk menghitung jumlah kali membaca huruf 'a' dan berapa kali ia membaca huruf 'b' pada urutan pertama untuk mengetahui nilai n dan m .

Jika r> 1 maka lain yang sama urutan huruf 'a' dan huruf 'b' diharapkan.

Jika otomat / mesin tidak tahu berapa banyak huruf 'a' dan huruf 'b' itu dibaca dalam urutan pertama maka itu juga tidak tahu nilai n dan m dan dengan demikian itu tidak bisa memberi tahu apakah urutan lainnya dari kedua ke terakhir adalah kata-kata yang sama dengan urutan pertama.

Tetapi diketahui bahwa hanya mesin Turing yang dapat menghitung dan mengetahui nilai n dan m serta mengenali bahasa di atas, sehingga tidak hanya bahasa di atas tidak biasa, tetapi juga tidak bebas konteks, yaitu juga tidak tidak ada automat pushdown untuk mengenali bahasa ini dan tidak ada tata bahasa bebas konteks yang setiap kata yang berasal dari konteks tata bahasa bebas ada dalam bahasa di atas.

Karena fakta bahwa kedua otomat hingga deterministik dan otomat hingga pushdown tidak dapat menghitung dan mengetahui nilai n dan m , tidak seperti mesin Turing, mereka tidak dapat mengenali bahasa di atas dan dengan demikian bahasa di atas tidak bebas konteks dan tidak biasa.

Tolak sampel dengan asumsi bahwa bahasa di atas teratur:

Untuk n = 3 ∧ m = 5 ∧ r = 2 , kata berikut dalam bahasa di atas:

aaabbbbbaaabbbbbb

Tetapi kata berikut ini tidak ada dalam bahasa:

aaabbbbbaaaaabbb, karena tidak ada n, m dan r jadi:

(a ⁿ b ^m ) ^r = aaabbbbbaaaaabbb, karena untuk memenuhi urutan pertama huruf 'a' dan kemudian huruf 'b', harus benar bahwa n = 3 ∧ m = 5 , dan karena itu kita melihat 2 urutan huruf ' a 'dan kemudian huruf' b ', lalu r = 2 , tetapi jika n = 3 ∧ m = 5 ∧ r = 2 maka (a ⁿ b ^m ) ^r = (a ³ b ⁵ ) ² = (aaabbbbbb) ² = aaabbbbbaaabbbbbbbbbbbb ≠ aaabbbbbaaaaabbb, karena sufiksnya berbeda, yaitu aaabbbbb ≠ aaaaabbb, meskipun awalannya sama dengan aaabbbbbb untuk r = 1.

Otomat terbatas deterministik "terbaik" yang dapat dibangun untuk bahasa ini adalah otomat terbatas deterministik yang mengenali ekspresi reguler (a * b *) *, tetapi ia tidak mengenali bahasa di atas, karena ia memberi tahu kedua kata tersebut aaabbbbbabaababbbbb dan aaabbbbbaaaaabbb dalam bahasa dan ini tidak benar, karena aaabbbbbbaaabbbbb dalam bahasa, tetapi aaabbbbbaaaaabbb tidak dalam bahasa.

Bahkan otomat terbatas pushdown tidak dapat memastikan apakah kedua kata dalam bahasa atau tidak, jadi hanya mesin Turing yang bisa.

Pada urutan kedua, mesin Turing menemukan bahwa n = 5 ∧ m = 3 dan ini bertentangan dengan urutan pertama yang ditemukan bahwa n = 3 ∧ m = 5 , sehingga ia memberi tahu bahwa kata kedua tidak dalam bahasa. , tetapi tidak ada kontradiksi yang ditemukan pada kata pertama.

Kedua urutan memuaskan bahwa n = 3 ∧ m = 5 , sehingga mesin Turing mengatakan bahwa kata pertama ada dalam bahasa.

Hanya mesin Turing yang dapat, jika menghitung dan mengingat nilai n dan m dengan menuliskan nilainya pada kaset itu dan kemudian membacanya.

Perpisahan Stack Exchange
sumber