Pertimbangkan mesin keadaan terbatas seperti biasa, tetapi setiap transisi, ia juga dapat memperbarui penghitung bilangan bulat dengan menambahkan atau mengurangi angka. Katakanlah, fungsi transisi dari bentuk pindah ke keadaan baru p , dan tambahkan k ke penghitung, di mana k ∈ Z (jadi k dapat positif, negatif, atau nol) .
Suatu string diterima jika keadaan akhir dan nilai penghitungnya dalam , di mana F adalah himpunan pasangan kondisi dan nilai penghitung yang terbatas.
Apakah model ini dikenal? Saya tidak dapat menemukan referensi ekstensi khusus ini.
finite-automata
Chao Xu
sumber
sumber
Jawaban:
Dengan anggapan dapat berupa bilangan bulat apa pun, maka ini dapat diformalkan sebagai otomat satu arah yang buta . Biasanya automata ini menerima pada kondisi akhir ketika penghitungnya nol, tetapi kami dapat dengan mudah memodelkan jenis penerimaan Anda jika Anda mengizinkan transisi ϵ (yang tidak mengkonsumsi input). Jika saya tidak salah, seperti dengan automata keadaan terbatas, seseorang dapat menyingkirkan ϵ , tetapi itu adalah hasil yang tidak sepele.k ϵ ϵ
Ada beberapa jenis automata satu-counter. Dalam bentuk yang paling umum mereka diizinkan untuk menguji apakah nilai penghitung sama dengan nol. Bahasa yang mereka terima adalah bagian ketat dari bahasa bebas konteks.
Model yang mungkin Anda cari disebut blind , tidak dapat menguji nol, kecuali sebagai tes akhir untuk penerimaan di akhir perhitungan.
sumber
Model ini adalah varian automata tertimbang, yang dipelajari secara luas (walaupun ada banyak pertanyaan terbuka tentang mereka). Anda bisa mulai di sini: Buku Pegangan Automata Berbobot .
Perhatikan bahwa kadang-kadang mereka disebut "distance automata" (meskipun ini menjadi kurang umum).
sumber