Informatiker Board | Theoretische Informatik | Eindeutigkeit von kontextfreie Grammatiken

Informatiker Board » Themengebiete » Theoretische Informatik » Eindeutigkeit von kontextfreie Grammatiken

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Eindeutigkeit von kontextfreie Grammatiken

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

ynynloxx
Grünschnabel

Dabei seit: 28.06.2017
Beiträge: 1

Eindeutigkeit von kontextfreie Grammatiken

Zitatantwort auf diesen Beitrag erstellen

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.

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ynynloxx: 28.06.2017 12:41.

28.06.2017 12:41

Nehmen Sie ynynloxx in Ihre Freundesliste auf

meandmyself
Grünschnabel

Dabei seit: 16.08.2017
Beiträge: 1

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 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

16.08.2017 15:55

Nehmen Sie meandmyself in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Eindeutigkeit von kontextfreie Grammatiken