 Chomsky-Normalenform |
KleenEule
Grünschnabel
Dabei seit: 19.06.2011
Beiträge: 7
 |
|
Hey Leute.
Wir haben heute die Chomsky-Normalenform gemacht und unser Tutor hatte uns zum überlegen folgende Aufgabe gegebe (Keine Sorge, die dient nicht der Abgabe oder so, er möchte uns einfach nur mehr Aufgaben geben zum üben):
Gib äquivalente Grammatiken in Chomsky-Normalform für folgende kontextfreie Grammatiken
G = (V; T; S; P) an.
1. G1 = ({S}, {0,1}, S, {S -> µ, S -> 0, S->1, S -> 0S0 , S -> 1S1})
Jetzt muss man ja in 4 Schritten vorgehen:
1. Alle Terminale in die Form Y_0 bringen mit Y_0 -> 0
2. Alle nebeneinander stehenden Variablen der Rechten Seite zusammenfügen.
3. Entfernen der epsilon - Regeln : Hier werden alle Regeln A -> µ , außer S' -> µ gestrichen. Für jede Regel, die ein solches A auf der rechten Seite enthält, wird eine Regel hinzugefügt, in der das A gestrichen wurde.
4. Beseitigung der Kettenregeln
Wir kamen leider nicht mehr dazu, diese Aufgabe in der Stunde durchzurechnen (er will es nächste mal tun), aber mich würd das jetzt schon interessieren, zumal es für den Übungszettel morgen hilfreich wäre, wenn ich die Chomsky-Normalenform draufhabe
Jetzt habe ich doch iwie Probleme, dieses Verfahren so darauf anzuwenden. Kann mir das vllt jmd mal anhand dieses Beispieles erklären?
|
|
21.06.2011 14:55 |
|
|
KleenEule
Grünschnabel
Dabei seit: 19.06.2011
Beiträge: 7
|
|
Ich habe mich nun mal vorrangearbeitet, aber bei Schritt 3 (epsilon-Regel entfernen) , da komm ich nicht vorran!
Wenn ich eine Epsilonregel entferne, was muss ich dann dahinschreiben , bzw. wie notiere ich das?
G1 = ({S}, {0,1}, S, {S -> µ, S -> 0, S->1, S -> 0S0 , S -> 1S1})
S -> µ
S -> 0
S -> 1
S -> 0S0
S -> 1S1
Schritt 1:
Y0 -> 0
Y1 -> 1
S -> µ
S -> Y0
S -> Y1
S -> Y0SY0
S -> Y1SY1
Y0 -> 0
Y1 -> 1
Schritt 2:
E -> SY0
F -> SY1
S -> µ
S -> Y0
S -> Y1
S -> Y0E
E -> SY0
S -> Y1F
F -> SY1
Y0 -> 0
Y1 -> 1
Schritt 3:
Schritt 4 ist nicht nötig, da es hier keine Ketten und Kreise gibt..
Anmerkung: µ = epsilon
Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von KleenEule: 21.06.2011 15:39.
|
|
|
21.06.2011 15:35 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
laut der Definition unseres Profs ist es so, dass man die Epsilonfreie Grammatik erreicht, indem man Epsilon-Produktionen dadurch entfernt, in dem man jedes vorkommen von X->u eps v durch X->uv ersetzt und X->eps streicht. Das Trifft auch auf S->eps zu.
Exisitert ein S->eps dann führt man einen neuen Startzustand S' ein. Weiterhin werden die Produktionen S'
->eps und S'->S in die Menge der Produktionen aufgenommen.
Vlt ist es das was euch noch fehlt...
VG,
Karlito
|
|
|
22.06.2011 01:04 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Sorry, die Beschreibung war nicht ganz richtig,
Folgendes Beispiel: S->eps, S->aSa
1. Neue Produktionen hinzufügen, welche entstehen würden, wenn man epsilon produktion anwendet
=> S->eps, S->aSa, S->aa
2. eps Produktionen entfernen
=> S->aSa, S->aa
3. Wenn die Sprache leer sein konnte (S->eps enthalten, S= Startzustand), dann S' einführungen mit S'->eps und S'->S
=> S'->eps, S'->S, S->aSa, S->aa
Ich hoffe das macht es klar.
VG,
Karlito
|
|
|
22.06.2011 18:04 |
|
|
KleenEule
Grünschnabel
Dabei seit: 19.06.2011
Beiträge: 7
|
|
Ahhh okay, das macht die Sache auf jeden Fall klarer!
Weil unsere Professorin hat zu diesem Thema nur gesagt "Wird weggestrichen" , was nicht super viel geholfen hat... 
Danke dir!
|
|
|
23.06.2011 17:38 |
|
|
|
