darf eine kontextsensitive Grammatik Produktionen der Form N0 -> 0N haben?

Question

hey,

darf eine kontextsensitive Grammatik Produktionen der Form N0 -> 0N haben? Dass monotone Grammatiken jene Produktion haben dürfen ist mir klar, aber die Definition von kontextsensitiven Grammatiken besagt doch gerade, dass die Terminalzeichen um das Nonterminalzeichen herum nicht verändert werden dürfen?

 

Answer 1

Nein, solch eine Produktion ist in einer kontextsentitiven Grammatik nicht erlaubt. Allerdings existiert zu jeder monotone Grammatik eine äquivalente kontextsentive Grammatik (Kap.4 , Folie 2). Ein Beispiel (Produktion: Fb -> bF) für solch eine Umwandlung wird auf den beiden nachfolgenden Folien (Kap. 4, Folien 3 und 4) gezeigt.

Gruß,

Tobias (Tutor)