Chomsky-Normalenform |
| 21.06.2011, 14:55 | Auf diesen Beitrag antworten » |
| KleenEule | Chomsky-Normalenform 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, 15:35 | Auf diesen Beitrag antworten » |
| KleenEule | 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 |
| 22.06.2011, 01:04 | Auf diesen Beitrag antworten » |
| Karlito | 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, 18:04 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| Anzeige | |
|
|
|
| 23.06.2011, 17:38 | Auf diesen Beitrag antworten » |
| KleenEule | 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! |
|
|