Warum ist hier die Grammatik nur vom Typ 0 und nicht auf vom Typ 1?

Question

Ich hab eine Frage zu c) und d) Teil

1) Warum ist hier die Grammatik nur vom Typ 0 und nicht auf vom Typ 1? Verstehe auch hier die Begrüdnung " i = 0. Denn es gibt nicht-kontextfreie, verkürzende Regeln." nicht. Ja, das ist mir klar, dass diese Grammatik wegen Umformungen wie "aTb -> ab" nicht kontextfrei sein kann. Aber aus welchem Grund sollte diese Grammatik nicht kontextsensitiv sein? Welche kontextsensitive Regel sollte denn hier verletzt werden?

2) Auch der d) Teil verwirrt mich sehr. Seit wann ist denn die Chomsky-Normalform kontextfrei? Meines Wissens dürfen in der Chomsky-NF keine Umformungen der Form A-> bAb stehen, wie es bei kontextfreien der Fall ist. Ich bin bisher immer davon ausgegangen, dass die CNF rechtslinear, also vom Typ 3 ist.

Dass die Grammatik G nicht in CNF umgeformt werden kann, liegt doch auch daran, dass links 2 N stehen und es deshalb nicht möglich ist, diese Grammatik mit den 4-Schritten umzuformen (habe es probiert).

Ich bitte um Aufklärung, da mich diese Aufgabe gerade komplett verwirrt und alles Gelernte durcheinander wirft

Answer 1

Hallo,

 

1) Hier handelt es sich nicht um eine kontextsensitive Grammatik, denn wenn du dir die Definition von Typ-1 Grammatiken anschaust, dann besagt sie:

(phi1)A(phi2) --> (phi1)(PSY)(phi2) mit PSY ungleich lambda. Bei der Regel die du genannt hast wird aber gerade T auf lambda abgebildet.

Desweiteren ist die Grammatik auch nicht kontextfrei/vom Typ 2. Denn kontextfreie Grammatiken sind von der Form

A->PSY, d.h. auf der linken Seite der Regeln steht immer nur ein NT.

 

2) Da hast du was verwechselt. Eine kontextfreie Grammatik muss zwar nicht in CNF vorliegen. Dafür ist aber die CNF kontextfrei (schau dir Definitionen mal an, dann wirst du feststellen, dass CNF ein Spezialfall von Typ-2 Grammatiken ist). Das ist kein Widerspruch. Rechtslinear ist eine CNF i.A. nicht, denn bei rechtslinearen Grammatiken erlaubst du Regeln der Form A-->aB und die sind verboten in der CNF.

 

Viele Grüße,

Vivian (Tutor)