Saya bingung tentang contoh yang diberikan dalam artikel Wikipedia tentang tata bahasa konteks-sensitif:
https://en.wikipedia.org/wiki/Context-sensitive_grammar
Disclamer : Saya sudah mengubah bagian yang dibahas di artikel wikipedia, jadi keadaan artikel saat ini akan berbeda dari yang saya bahas dalam pertanyaan ini. Versi asli ada di sini: https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366
Tata bahasa berikut, dengan simbol awal S, menghasilkan bahasa non-konteks kanonik {anbncn: n ≥ 1}:
- S → abc
- S → a SB c
- c B → WB
- WB → WX
- WX → BX
- BX → B c
- b B → bb
Mereka tidak mengklaim secara langsung bahwa tata bahasa ini peka konteks , tetapi kalimat berikutnya menyiratkan bahwa mereka menganggapnya peka konteks :
aturan 3 hingga 6 memungkinkan untuk bertukar berturut-turut setiap cB ke Bc (empat aturan diperlukan untuk itu karena aturan cB → Bc tidak akan masuk ke dalam skema αAβ → αγβ)
Jadi mereka naik banding ke bentuk kanonik aturan tata bahasa konteks-sensitif: αAβ → αγβ, menyiratkan bahwa seluruh tata bahasa adalah konteks-sensitif.
Yang saya bingung adalah aturan # 3 , yang sepertinya tidak cocok dengan skema αAβ → αγβ. Saya menganggap terminal sini sebagai bagian dari , variabel sebagai skema , kosong. Ini menyiratkan bahwa tidak dapat menghasilkan , karena harus disimpan di tempat yang sama ( ).α B A β c B W B c c B → c …
Apakah saya melewatkan sesuatu atau tata bahasa ini benar-benar ditempatkan di sini secara keliru (karena tidak peka konteks nyata)?
sumber
Jawaban:
Jika saya tidak salah, tata bahasa CS yang lebih sederhana adalah mungkin. Ini dia:
sumber
Sebenarnya beberapa pemirsa sepakat tata bahasa asli salah. Seperti yang diperhatikan oleh @ EmilJeřábek, sudah ada diskusi tentang masalah ini di sini: https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language
Jadi tampaknya tidak ada tata bahasa 7 aturan (yang saya tanyakan di atas dalam pertanyaan saya), tidak ada tata bahasa 9 aturan yang ada di sini sebelum dan hadir dalam artikel bahasa lain, keduanya tidak benar. Tata bahasa 9-aturan ini:
aaa bb cccc
Jadi saya sarankan mengikuti peningkatan tata bahasa ini dengan mengganti aturan 3-5 hingga empat aturan:
Aturan 3-6 akan membantu menghindari masalah dengan mengganti CB ke WB dan kemudian WC ke BC.
sumber