Mesin untuk bahasa bebas konteks yang tidak memperoleh daya ekstra dari nondeterminisme

21

Ketika mempertimbangkan model mesin dari perhitungan, hierarki Chomsky biasanya ditandai oleh (dalam urutan), automata terbatas, automata push-down, automata terikat linier dan Mesin Turing.

Untuk level pertama dan terakhir 1 (bahasa reguler dan bahasa yang berulang secara berulang), tidak ada bedanya dengan kekuatan model apakah kami mempertimbangkan mesin deterministic atau nondeterministic, yaitu DFAs setara dengan NFA, dan DTM setara dengan NTMs 2 .

Namun untuk PDA dan LBA, situasinya berbeda. PDA deterministik mengenali serangkaian bahasa yang lebih kecil daripada PDA non-deterministik. Ini juga merupakan pertanyaan terbuka yang signifikan apakah LBA deterministik sekuat LBA nondeterministik atau tidak [1].

Ini memunculkan pertanyaan saya:

Apakah ada model mesin yang mencirikan bahasa bebas konteks, tetapi yang non-determinisme tidak menambah kekuatan tambahan? (Jika tidak, adakah properti CFL yang menunjukkan alasan untuk ini?)

Tampaknya tidak mungkin (bagi saya) bahwa dapat dibuktikan bahwa bahasa bebas konteks entah bagaimana memerlukan nondeterminisme, tetapi tampaknya tidak ada model mesin (dikenal) yang mesin deterministiknya cukup.

Pertanyaan ekstensi sama, tetapi untuk bahasa yang peka konteks.

Referensi

  1. S.-Y. Kuroda, "Kelas Bahasa dan Linear Bound Automata" , Informasi dan Kontrol, 7: 207-223, 1964.

Catatan kaki

  1. Pertanyaan sampingan untuk komentar, apakah ada alasan untuk level (dipesan dengan set inklusi) dari hierarki Chomsky menjadi nomor 3 hingga 0, bukannya 0 hingga 3?
  2. Untuk lebih jelasnya, saya berbicara tentang bahasa yang hanya dapat dikenali. Jelas pertanyaan kompleksitas secara radikal dipengaruhi oleh perubahan seperti itu.
formal-languages computability context-free computation-models context-sensitive Luke Mathieson
sumber
1
Jadi Anda meminta kelas bahasa yang lebih besar dari (tetapi sedekat mungkin) CFL yang versi deterministik = versi nondeterministik?
Ryan
@Ryan tidak, saya bertanya apakah ada model mesin yang mencirikan CFL, tetapi untuk varian nondeterministic dan deterministik yang setara dalam kekuasaan, Namun dengan asumsi tidak ada jawaban positif (yang saya kira tidak ada), itu bagus Pertanyaan lanjutan.
Luke Mathieson pada
3
Saya pikir masalah utama dengan pertanyaan adalah kurangnya definisi umum untuk "model komputasi". Anda bisa, misalnya, mendefinisikan TM deterministik yang dilengkapi dengan grammer bebas konteks, yang menerima kata jika tata bahasa menghasilkannya. Ini adalah model deterministik yang setara dengan CFL, tapi itu konyol ...
Shaull
@ Samull, itu poin yang adil, tetapi tampaknya sulit untuk memberikan definisi untuk model "masuk akal". Teladan Anda jelas terasa tidak wajar, tetapi saya tidak berpikir ada cara definisi yang dapat dibenarkan di sekitarnya.
Luke Mathieson pada
Untuk menghubungkan dalam pertanyaan tindak lanjut Ryan , mesin yang disebutkan dalam jawaban Thomas Klimpel (walaupun tidak seanggun PDA), akan cocok dengan gagasan "alami" dengan cara yang tidak dibatasi oleh TM untuk menghitung CFG. Mungkin intuisi adalah bahwa TM dengan CFG secara eksplisit mengkode dalam definisi CFL, sedangkan itu tidak jelas, misalnya, bahwa CFG dan PDA harus terkait, PDA adalah perpanjangan alami dari DFA dan kebetulan bekerja untuk CFL .
Luke Mathies pada

Jawaban:

-2

Dalam pemahaman saya tentang teori perhitungan, satu-satunya situasi non-determinisme tidak memberi Anda fleksibilitas ekstra (yaitu, .. kekuatan) adalah pada tingkat enumerable / rekursif rekursif. Ini terutama karena masalah penghentian dan keterbatasan pada kemampuan TM dalam decidability, yang saya yakin ini menjawab salah satu pertanyaan Anda di catatan kaki serta bilah sisi. Hierarki Chomsky adalah representasi logis dari peningkatan fleksibilitas yang terakhir (jika saya katakan), memungkinkan lebih banyak daya ke mesin. Apakah ini membantu pertanyaan / pikiran Anda?

Sejauh PDA dan LBA saya akan memiliki orang-orang ulung lainnya di sini di komunitas membantu dengan itu, pengalaman saya lebih banyak dengan TM dan teori yang terkait dengan bagian hierarki yang lebih tinggi (lebih banyak RE) (setidaknya seperti yang diajarkan dalam sarjana saya).

Teori perhitungan Peter Linz

https://www.amazon.com/Introduction-Formal-Languages-Automata/dp/1284077241/ref=pd_sbs_14_img_0?_encoding=UTF8&psc=1&refRID=6AA9FQJWZZNZDTQ6Z3K4

bmc
sumber
Ini tidak menjawab pertanyaan. OP sudah mengetahui apa yang Anda tulis.
Yuval Filmus