Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

Mehrere Lösungen beim Erzeugen Rechtslinearer Grammatik?

0 Punkte
49 Aufrufe
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!
Gefragt 6, Dez 2018 in Band I, Kapitel 4 von uyvpi uyvpi Lernwillige(r) (120 Punkte)  

Eine Antwort

0 Punkte
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)
Beantwortet 6, Dez 2018 von ugiut ugiut Lernwillige(r) (440 Punkte)  
...