Vorgehensweise bei rechtslinearen Grammatiken

Question

Hallo, ich habe das Prinzip der rechtslinearen Grammatik nicht ganz verstanden und verstehe nicht wie man auf die Musterlösung kommt. Nun wollte ich fragen, ob es vllt ein Schema gibt an dem ich mich entlang hangeln kann?

 

Vielen Dank!

 

 

Comments

Auch ich wäre über ein Schema zur Findung einer rechtslinearen Grammatik sehr dankbar! (--> hier: wie ich Aufgabenteil c) am besten löse)

Answer 1

Man kann hier den Algorithmus von Folie 2-69 anwenden, das wäre ein Schema.

Die Nonterminalsymbole der Grammatik sind ja das Analogon zu den Zuständen eines endlichen Automaten, daher funktioniert diese Grammatik nach genau dem selben Prinzip wie die Grammatik. Die Terminalsymbole codieren, ob die bisher erzeugte Anzahl von Nullen gerade oder ungerade ist, wie die Zustände im Automaten.

viele Grüße,

Sven (Tutor)

Answer 2

Zunächst sollte man sich klar machen, dass bei rechtslinearen Sprachen folgende Analogien bestehen:

 

- Nonterminalsymbole entsprechen Zuständen des Automaten

 

- Startsymbol S entspricht dem Anfangszustand s0

 

Bei solchen Aufgaben, bei denen eine bestimmte Anzahl von 0, 1 oder sonstigen Terminalzeichen vorherrschen soll, greift insbesondere erstere Regel.

 

Grundgedanke hier: speichere Anzahl der 0 in einem Zustand.

 

Zustand s1 bedeutet ungerade Anzahl 0

 

Zustand s2 bedeutet gerade Anzahl 0

 

entsprechend überlegt man sich, dass beim Startsymbol S ja noch keine 0 geschrieben werden konnte, diese also die gerade Anzahl der 0 repräsentieren muss.

 

Sobald eine 0 kommt (durch Übergang S-->0A) geht man in den "Zustand über, der ungerade Anzahl repräsentiert", also A

 

Kommt erneut eine 0, wechselt man wieder den "Zustand"

 

 

 

Hoffentlich ist das jetzt klarer?

 

(Bem.: Weil hier das leere Wort nicht akzeptiert wird, ist die Anzahl der Nonterminalsymbole nicht gleich der Anzahl der Zustände des Automaten.)