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 sprachen minimierung nichtdeterministisch huffman fehler-in-aufgabe chomsky-normalform anwesenheitsübung rechtslinear heimübung flip-flop cocke-younger-kasami-algorithmus kontextsensitive-grammatik kontextfreie-grammatik huffman-kodierung hauptklausur fehlererkennbarkeit 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 klausureinsicht disjunktive-normalform pumping-lemma info-ii bussysteme rechnerarchitektur abzählbarkeit komplexitätsklassen ableitungsbaum vorlesungsaufzeichnung round-robin minimierung-endlicher-automaten chomsky-klassen binärzahl entscheidbar programmiersprachen entscheidbarkeit aufzählbarkeit stern-symbol automaten nukit-fragen bewertung zugriffsarten von-neumann-rechner umformung adressierung mengen binär-subtrahieren organsiation

Kategorien

2 Pluspunkte 0 Minuspunkte
74 Aufrufe

Guten Tag zusammen,

in der Lösung steht auf die Frage in welcher Nomalform es ist:

Typ 3 (rechtslinear); die Grammatik ist (wie jede Typ-3-Grammatik) in Greibach-Normalform

Dazu meine Frage: Müsste die GNF nicht λ-frei sein?

Laut Vorlesungsfolien gitl: L(G ́) = L(G) \ {λ} oder würfel ich da etwas durcheinander?

Grüße

 

in HU-2-4 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte

Hallo,

das ist so nicht richtig. Die GNF darf auf das leere Wort abbilden (vgl. Vorlesungsfolie 3-34). In dieser Vorschrift steht, dass phi ein Element von N* sein muss und N* bedeutet beliebig viele Nonterminalsymbole, da ist die 0 mit dabei.

Die rechtslineare Grammatik darf nicht auf das leere Wort abbilden. Das heißt aber nicht, dass es keine Nonterminale geben darf, die auf das leere Wort abbilden. Wenn du dir die Grammatik noch einmal anschaust merkst du, dass jedes S auf ein Terminal- und ein Nonterminalsymbol abbildet, das leere Wort kann also nicht produziert werden. Eine Vorschrift

S --> lamda 

würde dieser Vorschrift widersprechen und daher wäre das keine rechtslineare Grammatik. Da das leere Wort nicht abgebildet werden kann, ist dieses Kriterium jedoch erfüllt.

Max (Tutor)

 

von uafjv uafjv Tutor(in) (168k Punkte)  
0 0
Hallo,

bei Max Antwort ist ein bisschen was durcheinander geraten, aber das liegt daran, dass wir uns in der Lösung zur Aufgabe vertan haben.

Erstens dürfen Regeln der GNF NICHT das leere Wort erzeugen, denn es sind Regeln der Form

\( A \rightarrow a\phi \)

Ein Terminal \( a \in T\) muss also immer auf der rechten Seite dabei sein, auch wenn \( \phi \in N^{\star} \) leer ist.

Zweitens sind in rechtslinearen Grammatiken Regeln, die das leere Wort erzeugen, erlaubt. Es ist also genau umgekehrt.

Was die vorangegangene Frage angeht, hat der Fragesteller Recht. Die Aussage müsste sein: "die Grammatik ist FAST in Greibach-Normalform (wie jede Typ-3-Grammatik) - das Lambda müsste aber noch eliminiert werden".

Viele Grüße

Lukas König, Friderike Pfeiffer-Bohnen und Micaela Wünsche
...