Mehrere Lösungen beim Erzeugen Rechtslinearer Grammatik?

Question

Gibt es bei Aufgabe 33 (aber auch bei anderen Aufgaben aus diesem Kapitel) auch andere mögliche Lösungen?

Ich habe es so verstanden, dass bei dem Nonternimalzeichen, das einem Endzustand entspricht, immer unter anderem das leere Wort folgt. Ist das falsch?

Wäre bei Aufgabe 33 zum Beispiel auch folgende Lösung möglich?:

P = {S -> 0S l 1A,

        A -> 0B l 1S,

        B -> 0B l 1S l λ}

Vielen Dank!

Answer 1

Hallo,

es kann sehr wohl vorkommen, dass eine Sprache von mehreren Grammatiken beschrieben wird (In der Lösung der Aufgabe sind bereits 2 Grammatiken angegeben). Deine Lösung ist auch korrekt.

Wichtig ist zudem, dass eine Grammatik keinen "Endzustand" besitz, da sie keine Wörter erkennt sondern erzeugt. Wenn man eine Grammatik auf Basis eines Automaten aufstellt kann es sein, dass ein Nonterminalsymol dem Endzustand entspricht. Dazu kannst du dir die Lösung der Aufgabe 33 b) anschauen:

A "entspricht" hier $S_0$

B "entspricht" hier $S_1$

C "entspricht" hier $S_2$

In der Lösung siehst du allerdings, dass C hier keinen Lambdaübergang besitzt.

Viele Grüße,

Jannik (Tutor)