Aufgabe 29 c)

Question

Hallo,

die Lösung zur Aufgabe 29 c) ist folgende:

G=(N,T,P,S)

N={S,A}

T={0,1}

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

A -> 0S |1A | 0 }

Mir ist bewusst wie man bei der Produktion auf das "Unterstrichene" kommt: Dort bekommt doch der Knoten S2 theoretisch die Bezeichnung S und dem Knoten S1 wird die Bezeichnung A zugeordnet? Und somit kann man alles weitere aus dem Endlichen Automaten ablesen.

Wie kommt man aber von dem Endlichen Automaten auf die fett markierten Zahlen 1 und 0 in der Produktion?

Vielen Dank im Voraus!

Answer 1

Hallo,

du schreibst schon ganz richtig, dass S2 dem S und S1 dem A entspricht. Das Wort muss aber irgendwann enden (wenn das Wort in S2 ist/landet), ohne die fettgedruckten wären alle Worte unendlich lang und damit die Sprache falsch. Das Wort endet entweder mit einer 1 (dann muss es vorher im Zustand S/S2(/S0) gewesen sein) oder es endet mit einer 0, dass heißt, es muss vorher im Zustand A/S1 gewesen sein und die letzte 0 sorgt wieder für eine gerade Anzahl.

Der Knoten S0 ist in S integriert (kommt eine 1 bleibt man im Zustand oder das Wort ist bereits zu Ende, oder es kommt eine 0 und man wechselt in A. S-->lambda geht nicht, da S0 kein Endzustand ist).

Ich hoffe es ist nun klarer, wenn nicht schreibe einfach nochmal.

Viele Grüße und viel Erfolg beim Lernen

Anne (Tutorin)

Comments

Hallo,

ja ergibt alles Sinn. Dankeschön!
Probiert man generell den Knoten S0 in einen anderen zu integrieren?


Es gibt ja keine richtige Vorgehensweise oder Algorithmus um eine Grammatik zu erzeugen. Ich probiere meist mir anhand eines Endlichen Automaten die richtige Grammatik herzuleiten.
Ist das generell empfehlenswert oder gibt es noch andere "Tricks"/Vorgehensweisen die du eher empfehlen würdest?

Viele Grüße

---

Sich die Grammatik anhand des Endlichen Automaten herzuleiten ist ein guter Weg. Je nachdem kann man sich auch überlegen, welche Wörter der Automat allgemein zulässt (in dieser Aufgabe z.B. eine gerade Anzahl von 0en) und dann zu überlegen, wie man das mit einer Grammatik schafft (hier mit 2 Zuständen, die die Anzahl der 0en zeigt, ob sie gerade oder ungerade ist).

Allgemein kann man nicht sagen, dass S0 in einen anderen Zustand integriert werden soll. In dieser Aufgabe ergibt es Sinn, da man S0 nur benötigt, damit lambda nicht zur Sprache gehört, aber danach kommt man nie wieder zum Zustand S0. Ist S0 ein Endzustand oder führen Pfeile zum Zustand S0 kann man ihn nicht einfach integrieren. Es kommt also auf den Automaten an.

Insgesamt ist der beste Weg einfach zu üben (was du ja offensichtlich schon machst). Dann sieht man hoffentlich schneller ein Schema hinter dem Automaten und kann die Aufgabe gut lösen.