Übungsbuch 1 Aufgabe 30

Question

Hallo,

ich habe mir für diese Aufgabe zuerst einen endlichen Automaten überlegt, und diesen dann nach dem Muster der Vorlesung in eine rechtslineare Grammatik umgewandelt.

Ich habe beim Automaten quasi mit V einen "Point of no return" erstellt, wo man dann immer bleibt, wenn in der Vergangenheit vier Einsen eingegeben worden sind.

Dabei kam folgende Grammatik heraus:

 

G={N,T,P,S}

N={S,B,C,D,V}

T={0,1}

P = { S --> 0S | 1B | 0 | 1
         B --> 0S | 1C | 0 | 1
         C --> 0S | 1D | 0 | 1
         D --> 0S | 1V | 0
         V --> 0V | 1V | lambda }

 

Das angegebene Wort konnte ich damit korrekt ableiten. Wäre diese Lösung auch richtig?

Vielen Dank!

Answer 1

Leider reicht es nicht, dass du das Testwort mit deiner Grammatik ableiten kannst.

Du könntest mit dieser Grammatik zum Beispiel auch das Wort 11111 ableiten, welches nicht in der angegebenen Sprache liegt. Deshalb ist deine Lösung leider nicht  korrekt.

Viele Grüße, Julia (Tutorin)