|
|
Servus,
da kein Wort existiert für das es 2 Linksabl. gibt, ist die Grammatik eindeutig.
Dies würde ich persönlich ähnlich wie bei PCP zeigen.
Du schaust dir die einzelnen Produktionen an und stellst nach und nach fest, dass du keine Eindeutigkeit erreichen kannst.
Anschaulich: Zunächst fängst du mit S -> A -> aAa an. Hier stimmen folgenden Ableitungen mit dieser bis auf die Mitte über ein: S-> A->aca. Da du von A aber kein einzelnes c ableiten kannst, kannst du sagen, dass es für S->... aAa keine andere Linksableitung gibt.
Jetzt zum nächsten: S->A->abAb. Da alle rechten Seiten der Produktionen (bis auf S) 2 äußere Terminale (ich meine hier x,y für die Produktion Z -> x****y) enthalten, muss die rechte Seite deiner anderen Ableitung irgendwas mit aX***b (und X muss eine Ableitung nach b**** besitzen) sein oder ab****b. Dann überprüfst du wieder welche Abl. in Frage kommen. Du fängst mit der ersten an und wirst herrausfinden, dass du irgendwann ähnlich zu PCP zu einer Schleife gelangst. Also probierst du die nächste (Back-Tracking), auch hier wirst du zu einer Schleife gelangen. Das machst du mit allen möglichen Ableitungen von S (du kannst für die aus S->B natürlich schon die vorherigen Erkenntnisse von S->A verwenden).w
Am Ende hast du bewiesen, dass die Ableitungen paarweise eindeutig sind => alle Wörter, die in L(G) liegen lassen sich eindeutig ableiten => die Grammatik ist eindeutig.
Viele Grüße
|
|
