Kesalahan dalam contoh CSG Wikipedia?

8

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}:

  1. S → abc
  2. S → a SB c
  3. c B → WB
  4. WB → WX
  5. WX → BX
  6. BX → B c
  7. 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 cαBAβcBWBccBc

Apakah saya melewatkan sesuatu atau tata bahasa ini benar-benar ditempatkan di sini secara keliru (karena tidak peka konteks nyata)?

Andrey Lebedev
sumber
1
Saya pikir kamu benar.
Emil Jeřábek
@ EmilJeřábek Sepertinya kami membuat perubahan pada bagian artikel wiki pada saat yang sama: Saya telah memperkenalkan versi tata bahasa yang tepat
Andrey Lebedev
Sayangnya, tata bahasa Anda salah. Lihat en.wikipedia.org/wiki/… .
Emil Jeřábek
@ EmilJeřábek Maaf, ada apa dengan tata bahasa saya (9 aturan tata bahasa) yang saya tempatkan dalam versi artikel baru? Bisakah Anda menunjukkan aturan apa yang salah?
Andrey Lebedev
@ EmilJeřábek Ah, maksud Anda bahwa tata bahasa ini dapat menghasilkan "aaa bb cccc" juga?
Andrey Lebedev

Jawaban:

9

Jika saya tidak salah, tata bahasa CS yang lebih sederhana adalah mungkin. Ini dia:

  1. SABSc
  2. SAbc
  3. BAXA
  4. XAXY
  5. XYAY
  6. AYAB
  7. Aa
  8. Bbbb

aaabbbccc

1ABSc1ABABScc2ABABAbccc3AXABAbccc4AXYBAbccc5AAYBAbccc6AABBAbccc36AABABbccc36AAABBbccc7...aaaBBbccc8aaaBbbccc8aaabbbccc

Jeffrey Shallit
sumber
3

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:

  1. S → a BC
  2. S → a SBC
  3. CB → WB
  4. WB → WC
  5. WC → BC
  6. a B → ab
  7. b B → bb
  8. b C → bc
  9. c C → cc

aaa bb ccccanbncn

Jadi saya sarankan mengikuti peningkatan tata bahasa ini dengan mengganti aturan 3-5 hingga empat aturan:

  1. S → a BC
  2. S → a SBC
  3. CB → CZ
  4. CZ → WZ
  5. WZ → WC
  6. WC → BC
  7. a B → ab
  8. b B → bb
  9. b C → bc
  10. c C → cc

Aturan 3-6 akan membantu menghindari masalah dengan mengganti CB ke WB dan kemudian WC ke BC.

Bb

Andrey Lebedev
sumber