Apakah semua bahasa yang peka konteks dapat dipilih?

12

Saya sedang membahas definisi Wikipedia tentang bahasa yang peka konteks dan saya menemukan ini:

Setiap kategori bahasa adalah bagian yang tepat dari kategori yang tepat di atasnya. Otomat apa pun dan tata bahasa apa pun di setiap kategori memiliki otomat atau tata bahasa yang setara dalam kategori tepat di atasnya.

Saya dapat melihat bahwa otomat linear-terikat secara langsung di bawah penentu dalam pemesanan artikel. Jika ini masalahnya, maka itu berarti setiap perhitungan pada LBA akan berhenti di beberapa titik (karena setiap LBA akan menjadi penentu). Tetapi saya merasa bahwa mungkin ada beberapa perhitungan yang dapat berjalan pada LBA pada saat yang sama tidak pernah berhenti. Sebagai contoh, kita dapat menulis perhitungan pada LBA yang akan

  1. baca simbol pertama pada kaset itu dan bergerak ke kanan;
  2. baca simbol berikutnya dan kembali ke kiri.

Perhitungan (tidak berguna) ini (yang jelas merupakan perhitungan LB) akan berjalan tanpa batas ke kiri dan kanan dan tidak pernah berhenti dan karenanya tidak dapat menjadi penentu. Di mana saya salah berpikir?

formal-grammars turing-machines undecidability context-sensitive bongubj
sumber
1
Memutuskan CSL independen dari apakah ada LBA non-terminasi: hanya ada LBA untuk itu.
Raphael

Jawaban:

9

Pertama, semua bahasa yang peka konteks dapat dipilih, karena mereka dapat diterima oleh LBA (seperti yang Anda katakan), dan mesin Turing lebih kuat daripada LBA.

Namun, Anda bertanya tentang sesuatu yang lain. Mungkinkah ada LBA yang berputar? Jawabannya iya. Anda memberi contoh. Namun, Anda dapat memodifikasi setiap LBA ke mesin Turing yang menerima bahasa yang sama tetapi tidak pernah siklus. Untuk melihat ini, perhatikan, bahwa Anda dapat mensimulasikan pada dan melacak semua konfigurasi yang telah dicapai LBA sejauh ini. Jika ada satu konfigurasi yang muncul dua kali, Anda mendeteksi sebuah siklus. Dalam hal ini Anda berhenti menolak. Yang penting di sini adalah bahwa LBA menggunakan ruang linear, dan karenanya jumlah konfigurasinya dibatasi.MM′MM′

A.Schulz
sumber
Jika ada yang masih tidak mengerti jawaban ini, saya sarankan Anda merujuk ke Slide 3-4 dari presentasi ini untuk penjelasan tambahan.
bongubj
0

Saya sarankan Anda melihat buku ini: Pengantar Bahasa dan Teori Komputasi oleh John E Martin

halaman 283: Masih ada pertanyaan terbuka tentang bahasa yang peka konteks, seperti apakah setiap CSL dapat diterima oleh LBA deterministik.

Amir Nikabadi
sumber
Bagaimana ini menjawab pertanyaan? Bahasa yang peka terhadap konteks semuanya dapat ditentukan, terlepas dari apakah Anda memerlukan ruang linear deterministik atau nondeterministik.
Yuval Filmus