Chomsky-Normalform < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Wandeln Sie die kontextfreie Grammatik [mm] $G=(V,\Sigma,P,S)$ [/mm] mit [mm] $V=\{S,A,B\}$, $\Sigma=\{a,b\} [/mm] und [mm] $P=\{S \to ASA | aB, A \to B|S, B \to b|\epsilon\}$ [/mm] in Chomsky-Normalform um. |
Hi Leute!
Ich hab bei dieser Aufgabe an zwei Stellen Probleme, die ich euch in meiner Lösung zeigen werde. Ich würde mich auch sehr darüber freuen, wenn ihr mir sagen könntet, ob meine Lösung richtig ist und wenn nicht, woran es hakt!
1.) Eliminierung der [mm] $\epislon$-Regel:
[/mm]
[mm] $P=\{S \to ASA, S \to aB, A \to B, A \to S, B \to b, S \to a\}$
[/mm]
In diesem Schritt sollte wohl soweit alles in Ordnung sein.
2.) Eliminierung der Kettenregel:
[mm] $P=\{S \to ASA, S \to aB, A \to bB, B \to b, A \to aB, S \to a\}$
[/mm]
Die zwei Regeln von 1.) A->B und B->b, werden durch A->bB und B->b ersetzt. Das sollte passen. Ich weiß aber nicht ob die Regel A->aB richtig ist, die A->S und S->aB ersetzten soll.
3.) Separation von Terminalen und Nicht-Terminalen:
[mm] $P=\{S \to ASA, S \to V_a B, A \to V_b B, B \to b, A \to V_a B, S \to a, V_a \to a, V_b \to b\}$
[/mm]
Wenn 2.) richtig ist, sollte das hier nun auch richtig sein.
4.) Eliminierung von Nicht-Terminal-Ketten:
[mm] $P=\{S \to AS_1 S_1 \to SA, S \to V_a B, A \to V_b B, B \to b, A \to V_a B, S \to a, V_a \to a, V_b \to b\}$
[/mm]
Hier bin ich mir bei diesen Regeln nicht ganz sicher $S [mm] \to AS_1 S_1 \to [/mm] SA$, weil S nicht nur ein Nicht-Terminal ist, sondern das Startsymbol...; darf ich diesen Teil der Normalisierung auch einfach auf das Startsymbol anwenden?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:21 So 05.05.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:51 Di 07.05.2013 | | Autor: | bandchef |
Kann mir zu dieser Aufgabe wirklich niemand helfen?
|
|
|
|
