Bahasa apa yang dikenali oleh mesin satu-counter?

Mesin penghitung dengan dua atau lebih penghitung biasanya ditunjukkan setara dengan mesin Turing dalam kursus tentang teori perhitungan. Namun, saya belum melihat analisis formal yang bahasa dapat dikenali oleh mesin satu-counter. Apakah bahasa-bahasa ini setara dengan bahasa bebas konteks (mungkin oleh konstruksi cerdas yang mengaitkannya dengan PDA), atau apakah mereka merupakan kelas bahasa yang sama sekali berbeda?

One counter automata adalah pushata automata dengan hanya satu simbol yang diperbolehkan pada stack (ditambah simbol bottom tetap). Bahasa yang dikenali oleh satu counter automata membentuk subset yang tepat dari konteks bahasa bebas.

Misalnya automata 1-counter dapat mengenali bahasa yang tidak teratur, tetapi tidak dapat mengenali bahasa { a n b m a m b n } yang bebas konteks dan dapat dikenali oleh 2-counter automata juga.$\{a^nb^n\}$$\{a^nb^ma^mb^n\}$

Jika k-DCA adalah k-counter automata deterministik , dan k-NCA adalah k-counter automata nondeterministic , maka kami memiliki inklusi yang tepat sebagai berikut:

DFA (bahasa reguler) 1-DCA ⊂ 2-DCA$\subset$$\subset$

1-DCA 1-NCA$\subset$

Jika kita tidak mengizinkan transisi (beralih ke waktu nyata ) maka k-DCA ⊂ k'-DCA untuk k <k '.$\epsilon$$\subset$

Hanya untuk menyelesaikan: ada bahasa yang bebas konteks tetapi tidak dapat recgnized oleh automatas counter (k-DCA dengan k 2) (misalnya { w w R } ), dan bahasa diakui oleh automatas counter yang tidak bebas konteks (untuk contoh { a n b n c n } ). Counter automata (khususnya dua counter automata) dapat Turing lengkap hanya jika input dan outputnya disandikan dengan benar (lihat entri Wikipedia untuk detailnya).$\geq$$\{ww^R\}$$\{a^nb^nc^n\}$

Counter automata banyak dipelajari di masa lalu bahasa formal kuno, dalam konteks teori AFA dan AFL (keluarga abstrak automata & bahasa) oleh tim AS dan Prancis (Ginsberg, Greibach, ..., Nivat, Berstel, ...)

Counter automata biasanya didefinisikan sebagai automata keadaan terbatas yang dilengkapi dengan memori eksternal, yang terdiri dari bilangan alami (atau beberapa jika Anda memiliki lebih dari satu penghitung). Angka ini dapat ditambah, dikurangi, dan (biasanya) diuji nol. Perhitungan dimulai dengan nol dan hanya diterima ketika penghitungnya nol di bagian akhir, sebanding dengan penerimaan tumpukan kosong pushdown.

Jika mesin tersebut memiliki setidaknya dua penghitung seperti itu maka itu setara dengan mesin Turing, bahkan dalam kasus deterministik. Bukti dari fakta ini adalah oleh Minsky dan dapat ditemukan di artikel wikipedia yang Anda tautkan. Model ini tentu saja terkait dengan mesin register yang disebutkan di halaman wikipedia yang sama. Masalah pengkodean yang disebutkan dalam artikel wikipedia tidak penting dalam pengaturan ini di sini karena kami menganggap automata dengan rekaman input (setelah semua kita harus membaca string input) sedangkan wikipedia pada halaman ini hanya mengasumsikan penghitung.

Counter automaton ini dapat dilihat sebagai tipe khusus pda, hanya memiliki satu simbol stack, dan bottom-of-stack (yang tidak pernah dipindahkan). Ini memungkinkan otomat untuk menguji apakah penghitung / tumpukan adalah nol, dan bertindak sesuai.

Sebenarnya ada tiga jenis counter automata. Jadi gabungkan hasil dengan bijak atau Anda berakhir dengan kontradiksi (seperti yang terjadi pada saya di masa lalu). Ketiga jenis ini (secara ketat) termasuk dalam bahasa bebas konteks untuk one-counter.

Jenis di atas menyimpan bilangan bulat (atau angka alami, yang tidak masalah) dan dapat menguji isinya dengan nol. Blind toko kontra automata integer tapi tidak bisa tes untuk nol. Meskipun begitu, mereka dapat menghitung di bawah nol. Automata counter blind sebagian tidak dapat menguji nol, tetapi menyimpan nomor alami. Jika mesin mencoba untuk pergi di bawah nol, mesin akan berhenti tanpa menerima. Ini adalah jenis penyimpanan alami untuk memodelkan jaring Petri. Ia juga dihubungkan ke PDA, sekarang dengan simbol tumpukan tunggal tanpa penanda bawah khusus (dan karenanya masalah pengujian untuk nol: kami hanya terjebak ketika muncul elemen tumpukan terakhir). Terkadang nama-nama keluarga yang ditentukan oleh model penghitung respaktif adalah OCL, ROCL dan 1-BLIND.

$(Dc)^*$$D = \{ w\in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}$$a$$b$$c$

Sebagai contoh penelitian yang relevan, Latteux etal memiliki makalah nontrivial "Keluarga Bahasa Satu-Counter Ditutup di Bawah Quotient" (yang sebenarnya tentang ROCL).