Theoretische und technische Informatik - ganz praktisch - Letzte Aktivität in 2012-H-03

Beantwortet: 3a kontextsensitive Grammatik

Sun, 02 Feb 2020 11:09:19 +0000

Hallo,

Einen wirklichen Algorithmus gibt es dafür nicht. Was du jedoch oft machen kannst ist wenn du einmal ein Wort gefunden hast das gleiche Wort nochmal zu nehmen und in der Mitte einfach einen schritt doppelt machen (also zu pumpen) oft musst du dann nur die gleichen Schritte wie vorher erneut anwenden und kannst dann beliebig oft pumpen.

Constantin (Tutor)

Kommentiert: richtlineare Grammatik - CNF NK2011 Aufgabe 2d

Fri, 12 Feb 2016 19:09:33 +0000

Ah sorry. ich hab CNF und nicht GNF gelesen. Greibach-Normalform ist natürlich was anderes. Danke!

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

Sat, 10 Oct 2015 18:33:21 +0000

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)