Theoretische und technische Informatik - ganz praktisch - Letzte Fragen & Antworten in 2012-N-04

Beantwortet: alternative monotone Grammatik?

Tue, 29 Sep 2015 09:28:41 +0000

Deine Grammatik ist monoton. Leider erzeugt sie aber alle Wörter, die entweder ein a oder eine gerade Anzahl a's haben, nicht nur die jenigen, deren Zeichenanzahl eine Zweierpotenz ist.

Gruß,

Tobias (Tutor)

Beantwortet: Idee der Grammatik?

Tue, 29 Sep 2015 09:28:03 +0000

Die allgemeine Idee wird in den Hinweisen formuliert. Ich mache mal ein Beispiel mit der allgemeinen (korrigierten, s.o.) Grammatik, die Ableitung der Terminalworte lasse ich der Einfachheit halber weg:

S -> VAH (hat 1 A bzw. a.) -> VABH -> VBAAH -> VAAH (hat 2 A bzw. a) -> VAABH -> VABAAH -> VBAAAAH -> VAAAAH (4 A/a) usw.

Man sieht, dass man das B nur direkt vor dem H erzeugen kann und nur direkt hinter dem V wieder los wird, d.h. jedes erzeugte B muss einmal komplett durch die As geschoben werden. Das geht nur mit der Regel AB->BAA. Dadurch bekommt man für jedes A, an dem man das B vorbeischiebt, ein neues A hinzu. Insgesamt verdoppelt sich also die Anzahl der As mit jedem B, dass von hinten nach vorne wandert.

Tobias (Tutor)

Beantwortet: Wie bekommt man das B am Anfang wieder weg?

Tue, 29 Sep 2015 09:27:05 +0000

Hmm... Sieht aus, als ob Sie recht hätten. Ich glaube, den Fehler hatten wir schon einmal eliminiert, aber er hat sich offenbar wieder eingeschlichen. Wenn ich das richtig sehe, müsste das hier die korrekte Grammatik sein:

S => V,A,H
S => a
A,H => A,B,H
A,B => B,A,A
V,B => V
V =>
H =>
A => a

Haben Sie eigentlich mal unser Tool zum Testen von Grammatiken benutzt? Dort können Sie die obige Grammatik einfach einfügen und schauen, welche Wörter generiert werden: GrammarsPro.

Viele Grüße

Lukas König und Friederike Pfeiffer-Bohnen