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.)

Beliebteste Tags

verständnis alternativlösung klausur kellerautomat endlicher-automat grammatik regulärer-ausdruck pumpinglemma turingmaschine tipp zahlendarstellung cmos klausurrelevant bonusklausur komplexität schaltwerk binary-decision-diagram deterministisch assembler schaltnetz minimierung sprachen nichtdeterministisch huffman chomsky-normalform fehler-in-aufgabe anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik fehlererkennbarkeit huffman-kodierung hauptklausur vorlesungsfolien kontextfreie-sprache polynomialzeitreduktion faq gleitkommazahl fehlerkorrigierbarkeit rechtslineare-grammatik dateiorganisation cache darstellung-klausur nachklausur xwizard adressierungsarten lambda mealy konjunktive-normalform pipelining zustände saalübung leeres-wort endliche-automaten ohne-lösungen betriebssystem speicherorganisation moore monotone-grammatik 2-komplement fehler reguläre-sprache hammingzahl monoton lösungsweg pumping-lemma-für-kontextfreie-sprachen kodierung berechenbarkeit pumping-lemma klausureinsicht disjunktive-normalform info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

3 Pluspunkte 0 Minuspunkte
164 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!

 

 

in REC-AA von Dozent (10.1m Punkte)  
0 0
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 Pluspunkte 0 Minuspunkte

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)

von Dozent (10.1m Punkte)  
0 Pluspunkte 0 Minuspunkte
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.)
von Dozent (10.1m Punkte)  
...