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!
 

 

Vorgehensweise bei rechtslinearen Grammatiken

+3 Punkte
138 Aufrufe

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!

 

 

Gefragt 17, Okt 2014 in REC-AA von Lukas König Dozent (10,065,100 Punkte)  
Auch ich wäre über ein Schema zur Findung einer rechtslinearen Grammatik sehr dankbar! (--> hier: wie ich Aufgabenteil c) am besten löse)

2 Antworten

0 Punkte

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)

Beantwortet 17, Okt 2014 von Lukas König Dozent (10,065,100 Punkte)  
0 Punkte
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.)
Beantwortet 17, Okt 2014 von Lukas König Dozent (10,065,100 Punkte)  
...