Bahasa apa yang dibutuhkan untuk mengenali daftar yang dipesan? [multihead automata, rupanya]

8

Saya sedang mempertimbangkan masalah mengenali bahasa (lebih dari alfabet 0-9 dan spasi) yang mengandung string seperti "1 2 3 4 5 6" dan "14 15 16 17" tetapi tidak "1 3".

Ini muncul saat mengerjakan tugas parsing umum di mana elemen harus ada dalam daftar yang diurutkan. Saya tersadar bahwa ketika mem-parsing sisa bahasa itu adalah biasa, bagian ini jelas tidak teratur - ia dapat mengenali, misalnya, bahasa A1A2 di mana A adalah string acak 0-9. Bahkan tampaknya menjadi konten-sensitif (dan tidak bebas konteks oleh lemma pemompaan).

Pertanyaan pertama saya: adakah kelas bahasa (yang cukup dikenal, yaitu tidak didefinisikan hanya untuk masalah ini) antara peka konteks dan bebas konteks yang menggambarkan kekuatan ekspresifnya dengan lebih baik? Saya sudah membaca tentang bahasa yang diindeks Aho, tetapi tidak jelas (bagi saya!) Bahwa ini bahkan di kelas itu, meskipun kuat.

Pertanyaan kedua saya adalah informal. Tampaknya bahasa ini mudah diurai, namun sangat tinggi dalam hierarki. Apakah biasa menemukan contoh serupa dan apakah ada cara standar untuk menghadapinya? Apakah ada pengelompokan alternatif dari kelas bahasa yang tidak sesuai dengan inklusi pada yang 'biasa'?

Alasan saya untuk berpikir ini mudah: bahasa dapat diuraikan secara deterministik, dengan membaca sampai Anda mencapai akhir nomor pertama, memeriksa apakah nomor berikutnya mengikuti, dan sebagainya. Khususnya dapat diuraikan dalam O (n) waktu dengan O (n) ruang; ruang dapat direduksi menjadi tanpa terlalu banyak kesulitan, saya pikir. Tapi itu cukup sulit untuk mendapatkan kinerja semacam itu dengan bahasa reguler, apalagi bebas konteks.HAI(n)

fl.formal-languages Charles
sumber
Lemma pemompaan digunakan untuk membedakan bahasa bebas konteks dari bahasa reguler dan bukan dari bahasa konteks-sensitif. Jadi sudah pasti bahasamu tidak teratur, tapi kupikir itu bisa bebas konteks ...
Benoît Fraikin
2
@ Benoît Fraikin: Saya menggunakan lemma pemompaan 'yang lain'.
Charles
Lemma Bar-Hillel ... ini adalah kesalahpahaman saya ^ _ ^
Benoît Fraikin

Jawaban:

7

Kedengarannya seperti apa yang Anda cari adalah automata multihead (dalam kasus Anda, 1-way 2-way deterministic automata terbatas sudah cukup). Saya tidak benar-benar ahli dalam hal ini, tetapi google membuat beberapa survei menarik tentang hierarki bahasa ini, seperti

Marek Chrobak: Hirarki multihead automata satu arah, http://www.sciencedirect.com/science/article/pii/0304397586900939

Ini juga memberikan satu jawaban untuk pertanyaan kedua Anda: Hirarki n-head automata terletak "di" hierarki Chomsky.

Klaus Draeger
sumber
Benar-benar fantastis. Saya terkejut - dan senang - melihat keberadaan kelas semacam itu.
Charles
3
@Marek ada di situs ini: mungkin dia akan mempertimbangkan :)
Suresh Venkat
3
Makalah itu ditulis dalam kehidupan saya sebelumnya ;-) Ya, jika saya mengerti masalahnya, bahasa ini dapat diterima oleh robot 2 arah satu arah. Jadi itu juga di LOGSPACE.
Marek Chrobak