robot pushdown, dua bahasa dimungkinkan (kondisi OR)

Question

Dalam pekerjaan rumah kita harus membuat robot pushdown untuk 2 bahasa, tapi menurut saya ini adalah dua latihan dimana robot itu sama untuk keduanya.

Seperti yang saya pahami, kita dapat membuat robot pushdown non-deterministik, dan setiap kali kita membaca karakter a, kita dapat memasukkan satu A atau dua kali A - atas 'kebijaksanaan' robot itu.

Selanjutnya, sebuah status dibangun untuk karakter b, yang setiap kali dia membaca A dia akan menariknya keluar dari tumpukan. Dengan cara ini, automaton tahu bagaimana menangani kedua bahasa dimana jumlah a sama dengan jumlah b, dan juga bahasa dimana like a dua kali lipat jumlah b.

Apakah saya benar? Atau apakah saya melewatkan sesuatu?

Jika tidak, saya ingin sekali memahami cara menangani kondisi "atau" pada latihan pertama.

Terima kasih.

Answer 1

Sejak $L_2\ne L_3$, mereka jelas tidak dapat diterima oleh robot pushdown yang sama. Kedengarannya seperti yang ada dalam pikiran Anda adalah robot yang mengenali$L_3$. Mungkin cara termudah untuk mendesainnya untuk dikenali$L_2$, adalah merancang dua automata pushdown deterministik, satu untuk $\{a^nb^n:n\in\Bbb N\}$ dan satu untuk $\{a^{2n}b^n:n\in\Bbb N\}$. Kemudian gabungkan mereka menjadi satu robot pushdown yang memiliki transisi$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ dan $\langle q_0,\varepsilon,Z,q_2,Z\rangle$, dimana $q_0$ adalah keadaan awal dari PDA gabungan, $Z$ adalah simbol tumpukan awal, dan $q_1$ dan $q_2$adalah status awal dari dua anak perusahaan pushdown automata. Dengan kata lain, hal pertama yang dilakukan PDA gabungan adalah 'memilih' apakah akan mencari kata dari jenisnya$a^nb^n$ atau kata dari jenisnya $a^{2n}b^n$, dan kemudian mengejar pilihan itu secara deterministik.