\epsilon -Regel < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Gegeben sei die folgende Grammatik:
[mm] S\to [/mm] B0C | CB
[mm] B\to [/mm] 1B | [mm] \epsilon
[/mm]
[mm] C\to [/mm] 0C | DB
D [mm] \to [/mm] BD| [mm] \epsilon
[/mm]
Eliminieren Sie die [mm] \epsilon-Regeln. [/mm] |
Miau :3
da ich bei deraufgabe ein ziemlich "großes" Ergebnis habe wollte ich mal nachfragen, ob jemand das vielleicht überprüfen könnte.
also
Vor: G= (V, [mm] \sum [/mm] , P, S), V ={S, B, C, D} P = [mm] \begin{cases}S\to B0C \\ S \to CB \\ B\to 1B \\ B\to\epsilon \\ C\to 0C \\ C\to DB \\D \to BD \\ D\to \epsilon \end{cases}
[/mm]
erstmal die [mm] \epsilon [/mm] entfernen
[mm] P_1 [/mm] = [mm] \begin{cases}S\to B0C \\ S \to CB \\ B\to 1B \\ C\to 0C \\ C\to DB \\D \to BD \end{cases}
[/mm]
in [mm] V_1 [/mm] sind ja alle elemente, die auf epsilon abgebildet werden, oder welche, die nach einigen Ableitungen auf Epsilon abgebildet werden.
[mm] V_1 [/mm] ={B, D, C, S }
heißt also ich muss noch folgende Produktionen zu [mm] P_1 [/mm] hinzufügen
[mm] P_2 [/mm] = [mm] \begin{cases} S\to B0 \\ S \to 0C \\ S\to C \\ S\to B \\ B \to 1 \\ C \to 0 \\ C \to D \\ C \to B \\ D \to B \\ D\to D \end{cases}
[/mm]
[mm] D\to [/mm] D kann man weglassen oder?
und dann muss man noch
[mm] S\to \epsilon [/mm] hinzufügen, weil in der Sprache L(G) auch S [mm] \to [/mm] CB [mm] \to [/mm] C [mm] \to [/mm] DB [mm] \to [/mm] B [mm] \to \epsilon [/mm] funktionieren würde
mein Ergebnis für die Produktion ist also
[mm] P^2 [/mm] = [mm] \begin{cases}S\to B0C \\S\to B0 \\ S \to 0C \\ S\to C \\ S\to B \\S \to CB \\S\to \epsilon \\ B \to 1 \\ B\to 1B \\ C \to 0 \\ C \to D \\ C \to B\\ C\to 0C \\ C\to DB \\ D \to B \\ D\to D\\ D \to BD \end{cases}
[/mm]
Tut mit Leid ist ein bisschen unübersichtlich, aber wäre nett wenn jemand mal darüber schauen könnte :3
LG
Katze
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:22 Mo 25.04.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
