Dalam banyak makalah yang melibatkan tata bahasa bebas konteks (CFG), contoh-contoh tata bahasa yang disajikan di sana sering mengakui karakterisasi yang mudah dari bahasa yang mereka hasilkan. Sebagai contoh: S→aaSbS→aaSbS \to a a S b S→S→S \to menghasilkan {a2ibi|i≥0}{a2ibi|i≥0}\{ a^{2i}...
Saya bertanya-tanya, apakah ada makalah atau penelitian yang berhubungan dengan automata yang terlihat jelas, tetapi membiarkan kata-kata, daripada huruf tunggal, untuk didorong ke tumpukan. Bergantian, konstruksi yang memungkinkan untuk simbol harus didorong pada -transitions bisa mencapai tujuan...
EDIT (Oleh Tara B): Saya masih tertarik pada referensi ke bukti ini, karena saya harus membuktikannya sendiri untuk makalah saya sendiri. Saya mencari bukti Teorema 4 yang muncul di makalah ini: Hierarki Infinite dari titik-temu Bahasa Bebas Konteks oleh Liu dan Weiner. Teorema 4: Sebuah...
Biarkan menjadi bahasa bebas konteks. Tentukan menjadi penutupan sebelum dan postfix dari L , dengan kata lain, ppc (L) mengandung semua L 's prefiks dan postfixes, dan karenanya L sendiri. Pertanyaan saya: jika L bebas konteks dan memiliki tata bahasa yang tidak ambigu, apakah hal yang sama...
Saya ditanyai oleh siswa berikut, dan tidak dapat memberikan jawaban lengkap: Apakah ada properti penutupan untuk kelas bahasa yang tidak bebas konteks? Cukup mudah untuk menemukan contoh yang menunjukkan bahwa itu tidak ditutup di bawah persimpangan dan iterasi (operator bintang Kleene), tetapi...
Dalam pekerjaan saya muncul masalah klasifikasi CFL di bawah gambar fungsi rasional. Dalam istilah lain, apa kelas bahasa bahasa membentuk , untuk konteks tetap bahasa bebas L dan deterministik negara yang terbatas transduser T . Saya telah memperoleh beberapa hasil mudah seperti bahasa Dyck dengan...