Ich bin verwirrt über das Beispiel in einem Wikipedia-Artikel über kontextsensitive Grammatik:
https://en.wikipedia.org/wiki/Context-sensitive_grammar
Disclamer : Ich habe den besprochenen Abschnitt im Wikipedia-Artikel bereits geändert, sodass der aktuelle Status des Artikels von dem abweicht , was ich in dieser Frage diskutiere. Die Originalversion finden Sie hier: https://en.wikipedia.org/w/index.php?title=Context-sensitive_grammar&oldid=747616366
Die folgende Grammatik mit dem Startsymbol S erzeugt die kanonische nicht kontextfreie Sprache {anbncn: n ≥ 1}:
- S → abc
- S → a SB c
- c B → WB
- WB → WX
- WX → BX
- BX → B c
- b B → bb
Sie behaupten , nicht direkt , dass diese Grammatik ist kontextsensitive , aber im nächsten Satz impliziert, dass sie es als betrachten kontextsensitive :
Die Regeln 3 bis 6 ermöglichen den sukzessiven Austausch jedes cB gegen Bc (dafür sind vier Regeln erforderlich, da eine Regel cB → Bc nicht in das Schema αAβ → αγβ passen würde.)
Sie appellieren also an die kanonische Form kontextsensitiver Grammatikregeln: αAβ → αγβ, was impliziert, dass die gesamte Grammatik kontextsensitiv ist.
Habe ich etwas verpasst oder wurde diese Grammatik wirklich fälschlicherweise hier platziert (da sie nicht wirklich kontextsensitiv ist)?
quelle
Antworten:
Wenn ich mich nicht irre, ist eine einfachere CS-Grammatik möglich. Hier ist es:
quelle
Da sich mehrere Zuschauer einig waren, war die ursprüngliche Grammatik tatsächlich falsch. Wie @ EmilJeřábek bemerkte, wurde dieses Problem hier bereits diskutiert: https://en.wikipedia.org/wiki/Talk:Context-sensitive_grammar#Wrong_grammar_for_language
Es scheint also, dass weder die 7-Regel-Grammatik (die ich oben in meiner Frage abgefragt habe) noch die 9-Regel-Grammatik, die zuvor hier war und in Artikeln in anderen Sprachen vorhanden ist, beide falsch sind. Diese 9-Regel-Grammatik:
aaa bb cccc
Daher schlage ich vor, diese Grammatik zu verbessern, indem die Regeln 3-5 durch vier Regeln ersetzt werden:
Die Regeln 3-6 helfen dabei, Probleme beim Ersetzen von CB zu WB und dann von WC zu BC zu vermeiden.
quelle