Eindeutigkeit von kontextfreie Grammatiken

28.06.2017, 12:41	Auf diesen Beitrag antworten »
ynynloxx	Eindeutigkeit von kontextfreie Grammatiken Meine Frage: Die kontextfreie Grammatik lautet: S -> A \| B A -> aAa \| abAb \| bAc \| aca \| abcb \| bcc B -> bBa \| aBb \| babBc \| bca \| acb \| babcc Beweisen Sie entweder die Eindeutigkeit oder geben Sie zwei verschiedene Linksableitungen fur dasselbe Wort an. Meine Ideen: Guten Tag, habe eine Frage zu meine Hausaufgabe. Es ist gefragt ob eine gegebene kontextfreie Grammatik G eindeutig ist. Ich weiß dass eine Sprache eindeutig ist wenn es nur einen Ableitungsbaum für jedes Wort aus der Sprache gibt oder nur eine mögliche Linksableitung für ein Wort gibt, aber es ist kein Wort gegeben und ich weiß nicht wie man das formal richtig aufschreiben soll. Ich hatte mir überlegt die Aufgabe mir der Post'sche Korrespondenzproblem vielleicht anzugehen, weiß aber nicht wie man vorgehen soll. Hoffe mir kann einer helfen. Vielen Dank im Voraus.


16.08.2017, 15:55	Auf diesen Beitrag antworten »
meandmyself	RE: Eindeutigkeit von kontextfreie Grammatiken 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 aXb (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

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »