Bisakah automata bolak-balik satu arah dengan satu penghitung mengenali beberapa bahasa non-reguler yang tidak umum?

11

One-way alternating pushdown automata (1APDA) dapat mengenali bahasa apa pun di (Alternatif oleh Chandra, Kozen, dan Stockmeyer, 1981) . Dengan mengganti penyimpanan pushdown 1APDA dengan penghitung, kita bisa mendapatkan otomat bolak-balik satu arah dengan satu penghitung (1ACA). Pertanyaan saya adalah tentang 1ACA pada bahasa unary.DTsayaM.E(2HAI(n))

Bisakah 1ACA mengenali beberapa bahasa non-reguler unary ?

Perhatikan bahwa automata pushdown nondeterministic satu arah hanya dapat mengenali bahasa biasa yang unary.

Abuzer Yakaryilmaz
sumber

Jawaban:

6

Iya. Pertimbangkan bahasa dan buat automaton satu-konter satu arah yang mengenali dengan cara berikut. Pertama, otomat mulai meningkatkan nilai penghitung dan menebak kapan harus berhenti, yaitu menebak beberapa nilai . Kemudian ia bercabang secara universal: cabang pertama memeriksa bahwa panjang input tepat , dan cabang kedua bergerak sel maju pada input dan memeriksa bahwa sisanya berada di , dengan pergi ke keadaan kontrol awal. Sekarang tambahkan casing dasar: biarkan perangkat menerima jika pita input panjangnya tepatL.={Sebuahnn=2s,s0}L.m2mmL.1, dengan membuat perkiraan nondeterministic pada kondisi awal. Itu menyelesaikan konstruksi.

Dengan cara yang sama, orang bisa mendapatkan produk dari bentuk , dengan diperbaiki dan sewenang-wenang.n=k1s1...krsrk1,...,krs1,...,sr

dd1
sumber
1
Terima kasih atas jawabannya. Saya mendapat jawaban yang sama dari Pavol Duris (melalui komunikasi pribadi) yang akan segera muncul di koran. Saya berencana untuk mengirim jawaban setelah kertas muncul online. (Bahkan bisa ada beberapa hasil yang lebih kuat.) Bagaimanapun, jawaban Anda tentu diterima jawaban !
Abuzer Yakaryilmaz