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 endliche-automaten konjunktive-normalform pipelining zustände saalübung leeres-wort 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 entscheidbarkeit minimierung-endlicher-automaten chomsky-klassen von-neumann-rechner binärzahl entscheidbar programmiersprachen aufzählbarkeit stern-symbol automaten schaltnetze-und-schaltwerke nukit-fragen bewertung zugriffsarten umformung adressierung mengen binär-subtrahieren

Kategorien

0 Pluspunkte 1 Minuspunkt
169 Aufrufe
Hallo, ich hätte eine Frage zum Tutorium 2 Aufgabe 4b.

"(b) Bringen Sie die Grammatik durch „Scharfes Hinsehen“ in die Greibach-Normalform (GNF) und konstruieren Sie mit der neuen Grammatik einen Ableitungsbaum für folgendes Wort: axa−baxab"

Die Lösung lautet: 
P′ = { S → x|aAX|bAY |xB, 
          X → aB|a, 
          Y → bB|b
          B → −S
          A → x|aAC|bAD, 
          C → a
          D → b }

Ich kann absolut nicht nachvollziehen, wie man auf diese Regelmenge kommt. 
Ich war zwar in der Lage durch Anwendung der Regeln auf das Testwort zu kommen, musste aber dabei feststellen, dass viele der definierten Regeln garicht genutzt wurden (alles was unterstrichen wurde, habe ich für meine Umformung genutzt). 

(1) Zum Beispiel wurde die Definition "D → b " kein einziges mal verwendet, also warum wurde sie dann überhaupt definiert?

In der Lösung steht "bspw." also nehme ich an, dass es nur eine von vielen möglichen Definitionen für die Grammatik ist.

(2) Dennoch würde ich gerne wissen, welche Bedingungen eine solche Grammatik erfüllen muss, damit sie richtig ist?

(3) Hätte man also auch einfach die Definitionen weglassen können, die nicht unterstrichen sind?

Außerdem dachte ich, dass die vorherige Grammatik schon in GNF-Form ist. Ist nicht die GNF eine kontextfreie Grammatik, also eine Grammtik vom Typ 2.

(4) Warum ist "P = {S → A|A − S, 
                                A → x|aAa|bAb}" keine kontextfreie Grammtik?
Da sich doch hier auf der linken Seite nur Nonterminale und auf der rechten Seite eine nicht-leere Folge von N und T
 befindet.

Schonmal Danke für die Hilfe.
in AU-2-4 von uafjv uafjv Tutor(in) (168k Punkte)  

1 Eine Antwort

0 Pluspunkte 0 Minuspunkte
Hallo,

1. Nicht alle Regeln werden benutzt, denn es ist nur die Erzeugung von einem möglichen Testwort. Allerdings kann die Grammatik an sich viele weitere Worte erzeugen.
2. Bedingungen einer Greibach Normalform:Die Greibach Normalform erlaubt nur Regeln der Form N->TN*. Also ein nicht Terminalsymbol zu einem Terminalsymbol und beliebig viele nicht Terminalsymbole (beliebig(*) viele kann auch null bedeuten)
3. Man kann sie nicht einfach weglassen, weil die für weitere Worte nötig sein könnten. Natürlich gibt es mehrere Lösungen, aber man kann die Regeln nicht einfach weglassen nur weil sie für die Erzeugung von einem bestimmten Testwort nicht benutzt werden
4.  Das ist nicht in der Greibach Normalform, denn z.B S→A − S ist N→NTN und so eine Regel ist nicht erlaubt.
Man soll sich überlegen was bei einer Greibach Normalform erlaubt ist und dann die Regeln so umformen bis die die Bedingungen eine solche Form erfüllen.

Beste Grüße
Antonio (Tutor)
von uafjv uafjv Tutor(in) (168k Punkte)  
...