Hallo zusammen,
ich setzte mich gerade etwas mit der theoretischen Informatik auseinander und bin bei der Chomsky Hierachie angelangt.
Folgendes verstehe ich nicht:
Typ-2 Grammatiken (kontextfrei) sind eingeschränkter als Typ-1-Grammatiken (kontextsensitiv). Warum? Ich meine, bei kontextsensitiv ist doch die Einschränkung durch den Kontaxt gegeben, der bei kontextfrei fehlt.
Wäre für eine Erklärung dankbar!
Grüße,
Juli
Wohl weil alles, was als kontextfreie Grammatik formulierbar ist, formal auch als kontextsensitive Grammatik (die aber vom Kontext keinen Gebrauch macht) gesehen werden kann. Aber nicht umgekehrt.
Gruß, Lutz
Hallo,
die beiden Begriffe zielen auf die Art der Regeln ab.
Kontextfreie Regeln dürfen nicht den Kontext von Ersetzungen in Betracht ziehen. Deswegen steht auf der linken Seite immer ausschließlich ein Nicht-Terminalsymbol:
A -\> aBc
Kontextsensitive Grammatiken sind daran nicht gebunden und dürfen auf der linken Seite mehr stehen haben:
aBc -\> cBc
Kontextsensitive Grammatiken dürfen damit quasi Bedingungen einführen, die kontextfreien Grammatiken nicht zur Verfügung stehen.
Aus diesem Grund sind kontextsensitive Grammatiken ausdrucksstärker und damit allgemeiner als kontextfreie Grammatiken. Außerdem ist leicht ersichtlich, dass jede kontextfreie Grammatik auch eine kontextsensitive Grammatik ist.
Nico