Theoretische und technische Informatik - ganz praktisch - Letzte Fragen in 2012-H-03

3a kontextsensitive Grammatik

Sat, 01 Feb 2020 10:00:12 +0000

Hallo,

ich habe Schwierigkeiten auf die "komplizierteren" Wörter bei der 3a zu gelangen. Aktuell versuche ich es immer per "Ausprobieren", was allerdings nur bedingt erfolgreich ist. Gibt es einen Algorithmus dafür um sicher auf die Lösungen zu gelangen?

Viele Grüße

richtlineare Grammatik - CNF NK2011 Aufgabe 2d

Fri, 12 Feb 2016 18:29:58 +0000

Dann würde ich gerne wissen warum in der NK 2011 Aufgabe 2d steht,

"(d) Was muss man tun, um eine rechtslineare Grammatik in die Greibach-Normalform zu bringen?

Lösung: Nichts. "

Bedeutet das, dass rechtlineare Grammatiken nicht in CNF umgeformt werden kann?

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

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

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