CYK Wie elimiere ich ἑ

zumrut
Windoof-User
Windoof-User
Beiträge: 24
Registriert: 7. Feb 2008 09:49

CYK Wie elimiere ich ἑ

Beitrag von zumrut »

Haus übung 3

2. Schritt (elimiere ἑProduktionen):
Xo-> ZaXY I ZbXZb I a
X-> ZaXZa I ZbYI ἑ
Y->ZbXoZa I ZaXo
Za-> a
Zb-> b


Wie elimiere ich ἑ welche regel gibt.
wo gibt X das ist klar was dann wie geht weiter.


ich bedanke mich schon beantwort

DanielR
Mausschubser
Mausschubser
Beiträge: 83
Registriert: 19. Feb 2008 13:15

Re: CYK Wie elimiere ich ἑ

Beitrag von DanielR »

Um ε-Produktionen aus einer Grammatik zu entfernen ohne die Sprache L(G) zu verändern muss man ganz bildlich gesprochen folgendermaßen vorgehen:
Für jede Produktionsregel, in der eine Variable auf der rechten Seite vorkommt, die zu ε "werde kann" nimmt man eine neue Produktionsregel hinzu, die den Fall abdeckt das diese Variable "im nächsten Ableitungsschritt" zu ε wird: Dafür kopiert man die behandetle Produktion einfach und lässt die Variable auf der rechten Seite weg.

Ein kleines Beispiel:
Xo -> bX
X -> aX | ε
Diese reguläre Grammatik erzeugt die Sprache der {a,b}.Wörter, die mit einem b beginnen und dann beliebig viele a's haben L(G) = L(b(a)*).
Will ich nun die ε-Produktion löschen muss ich X ermöglichen nicht X->aX~>a (die Variable X ist beim geschwungenen Pfeil mit der ε-Produktion eliminiert worden) sondern auch direkt X->a abzuleiten. Wir fügen also eine zusätzliche Produktion ein
Xo -> bX
X -> aX | a | ε
Mit etwas Überlegen sieht man, dass wir damit auch Ableitungsketten der Art X->aX->aaX->.....->a....aX~>a...a eingeschlossen haben.
ε durften wir hier allerdings noch nicht entfernen, weil wir noch nicht alles beachtet haben: Es gibt die Produktionskette Xo -> bX ~> b. Wieder müssen wir die Möglichkeit bieten Xo->b abzuleiten. Dafür fügen wir die neue Produktion hinzu und können nun endlich die ε-Transition entfernen:
Xo -> bX | b
X -> aX | a
So haben wir eine aquivalente Grammatik ohne ε - Produktionen erzeugt.

Für das Ergebnis der Befreiung von der X->ε Produktion in der Hausübung möchte ich einfach nur auf die Musterlösung verweisen:
https://www3.mathematik.tu-darmstadt.de ... g3_sol.pdf

Antworten

Zurück zu „Archiv“