CNF < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:00 Sa 21.05.2011 | | Autor: | Katze_91 |
| Aufgabe | Transformieren Sie die Grammatik G = [mm] (V;\sum; [/mm] P; S) mit V = {S; A;B;C;D} und [mm] \sum [/mm] ={0; 1} und den Produktionen
S [mm] \to [/mm] 00B | 1A
A [mm] \to [/mm] B | C
B [mm] \to [/mm] 1B | 0 | AD
C [mm] \to [/mm] BD | AD
D [mm] \to \epsilon
[/mm]
in Chomsky-Normalform. |
Miau :3
beschäftige mich jetzt schon länger mit dieser Aufgabe und bin mir eigentlich ziemlich sicher, dass ich gerade ein ganzes Blatt umsonst geschrieben habe
bei einer CNF dürfen ja nur Produktionen A [mm] \to [/mm] AB oder [mm] A\to [/mm] a stehen
heißt also ich muss unteranderem die Epsilon Regel eliminieren
habe bei Wikipedia auch geschaut wie das geht und habe dann die Produktionen
S [mm] \to [/mm] EG
[mm] G\to [/mm] EB
[mm] E\to [/mm] 0
S [mm] \to [/mm] FA
[mm] F\to [/mm] 1
B [mm] \to [/mm] FB
[mm] B\to [/mm] 0
[mm] B\to [/mm] AD
C [mm] \to [/mm] BD
C [mm] \to [/mm] AD
[mm] A\to [/mm] FB
A [mm] \to [/mm] 0
A [mm] \to [/mm] AD
A [mm] \to [/mm] BD
[mm] B\to [/mm] BD
[mm] C\to [/mm] FB
C [mm] \to [/mm] 0
herausbekommen
hier ist mir dann aufgefallen dass ich D ja völlig streiche
könnte ich dann also einfach die CNF von
S [mm] \to [/mm] 00B| 1A
A [mm] \to [/mm] B|C
[mm] B\to [/mm] 1B|0|A
[mm] C\to [/mm] B| D
ausrechnen?
Vielen Dank Katze
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:14 So 22.05.2011 | | Autor: | felixf |
Miau!
> Transformieren Sie die Grammatik G = [mm](V;\sum;[/mm] P; S) mit V
> = {S; A;B;C;D} und [mm]\sum[/mm] ={0; 1} und den Produktionen
> S [mm]\to[/mm] 00B | 1A
> A [mm]\to[/mm] B | C
> B [mm]\to[/mm] 1B | 0 | AD
> C [mm]\to[/mm] BD | AD
> D [mm]\to \epsilon[/mm]
> in Chomsky-Normalform.
> Miau :3
> beschäftige mich jetzt schon länger mit dieser Aufgabe
> und bin mir eigentlich ziemlich sicher, dass ich gerade ein
> ganzes Blatt umsonst geschrieben habe
>
> bei einer CNF dürfen ja nur Produktionen A [mm]\to[/mm] AB oder
> [mm]A\to[/mm] a stehen
>
> heißt also ich muss unteranderem die Epsilon Regel
> eliminieren
> habe bei Wikipedia auch geschaut wie das geht und habe
> dann die Produktionen
>
> S [mm]\to[/mm] EG
> [mm]G\to[/mm] EB
> [mm]E\to[/mm] 0
> S [mm]\to[/mm] FA
> [mm]F\to[/mm] 1
> B [mm]\to[/mm] FB
> [mm]B\to[/mm] 0
> [mm]B\to[/mm] AD
> C [mm]\to[/mm] BD
> C [mm]\to[/mm] AD
> [mm]A\to[/mm] FB
> A [mm]\to[/mm] 0
> A [mm]\to[/mm] AD
> A [mm]\to[/mm] BD
> [mm]B\to[/mm] BD
> [mm]C\to[/mm] FB
> C [mm]\to[/mm] 0
>
> herausbekommen
>
> hier ist mir dann aufgefallen dass ich D ja völlig
> streiche
>
> könnte ich dann also einfach die CNF von
>
> S [mm]\to[/mm] 00B| 1A
> A [mm]\to[/mm] B|C
> [mm]B\to[/mm] 1B|0|A
> [mm]C\to[/mm] B| D
>
> ausrechnen?
Ja. Wenn nicht explizit gesagt wurde, dass ihr einen bestimmten Algorithmus anwenden muesst um "die" CNF zu finden, kannst du irgendeine kontextfreie Grammatik nehmen die die Sprache erzeugt und diese in CNF bringen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:45 So 22.05.2011 | | Autor: | Katze_91 |
miau :3
okay danke schön
werde einfach mal beides machen ^^
Liebe Grüße
Katze :3
|
|
|
|
