Unterschied kontextsensitive und monotone Grammatik?

Question

Hallo,

ich verstehe nicht ganz den Unterschied (falls es überhaupt einen gibt) zwischen kontextsensitiven und monotonen Grammatiken.

Ist jede kontextsensitive G auch monoton, aber nicht jede monotone G auch kontextsensitiv?
Wie kann man hier mit (echten) Teilmengen argumentieren? (Was ist (echte) Teilmenge von was?) Oder auch in Bezug zu Sprachen?

Gruß

 

Answer 1

Hallo,

das ist eigentlich ganz einfach:

• Kontextsensitive Grammatiken sind auch monoton (denn durch eine kontextsensitive Regel ϕAψ→ϕγψ wird immer ein einzelnes Zeichen A durch eine nichtleere Zeichenfolge γ ersetzt, also kann das Wort durch die Ableitung nicht kleiner werden).
• Monotone Grammatiken sind nicht unbedingt kontextsensitiv (denn eine Regel wie AB→BA ist nicht kontextsensitiv).

Entsprechend sind kontextsensitive Grammatiken eine echte Teilmenge der monotonen Grammatiken, ABER:

• Die Menge der durch monotone Grammatiken darstellbaren Sprachen ist gleich der Menge der durch kontextsensitive Grammatiken darstellbaren Sprachen. Beide Grammatiktypen können nämlich genau die Typ-1-Sprachen erzeugen.

Viele Grüße

Lukas König