Wie ergibt sich die Regelmenge?

Question

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.

Answer 1

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)