foogi
Jungspund
Dabei seit: 06.01.2007
Beiträge: 19
|
|
Eine Kontextfreie Sprache zur CNF |
|
hallo,
ich habe ein konteztfreie Grammatik, und ich möchte diese in ein Chomsky Normalform umwandeln.
Ich weiß das dies nicht schwer ist, doch habe ich kein ausführliches Beispiel gefunden.
ich habe also:
S--> AC
A--> aAb | epsilon
C--> cC | epsilon
Nun muss man ja die epsilon Regeln entfernen, Kettentregeln, und Hilfsregeln benutzten.
Wie würde das anhand diesem einfachen Beispiel funktionieren.
Eine Schrittweise erläuterung wäre sinnvoll, so das ich das nachvollziehen kann.
vielen Dank
|
|
10.01.2007 00:14 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
Ok, also zuerst machen wir deine Grammatik Epsilon-frei. Da du Epsilon ableiten kannst muss es auf jeden Fall die Produktion geben. Diese ist aber in CNF meines Wissens erlaubt.
Man entfernt das Epsilon durch eine einfache Regel:
Wird ein Nichtterminal A auf Epsilon abgeleitet, so ergänzen wir überall, wo A auf der rechten Seite vorkommt eine Regel, die A nicht enthält.
Eliminieren von
Eliminieren von
Nun führen wir für jedes Terminalsymbol ein Nichtterminalsymbol ein und ersetzen es überall dort, wo es gemischt mit Nichtterminalsymbolen vorkommt. Außerdem ergänzen wir die Regel .
Die Regel besteht aus drei Nichtterminalen. Das umgehen wir, indem wir einfach eine neue Produktion ergänzen und dann substituieren: . Dieses Verfahren kann man ggf. mehrfach anwenden.
Die Produktion eliminieren wir, indem wir einfach die Produktionen von A zu S überleiten: .
Ebenso verfahren wir mit :
Wir erhalten also:
Das sollte es sein (hoffe ich).
|
|
10.01.2007 02:01 |
|
|
|
foogi
Jungspund
Dabei seit: 06.01.2007
Beiträge: 19
|
|
|
10.01.2007 08:37 |
|
|
Jupi unregistriert
|
|
@Tobias
Besten Dank (7 Jahre später und immer noch aktuell)
|
|
12.11.2014 21:07 |
|
|
|
|
|