terminalsymbol < Logik < Logik+Mengenlehre < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:48 Di 09.01.2007 | | Autor: | AriR |
Hey leute,
gucke mir gerade bei wiki die chomskys normalform an und da steht, dass eine grammatik in CNF ist wenn jede ableitungsregel eine der folgenden formen hat:
1. A-->BC
2. A-->a
3. [mm] S-->\varepsilon
[/mm]
wobei A,B,C Nicht-Terminalsymbole sind und a ein Terminalsymbol und S das Startsymbol und [mm] \varepsilon [/mm] soll denke ich mal das leere Wort sein.
was ich nicht ganz verstehe ist die 3.regel. Die besagt doch erstmal nur, dass die Sprache auch leer sein kann oder?
außerdem muss man das doch nicht extra mit angeben oder? S gehört doch auch zu den Nicht-Terminalsymbolen und [mm] \varepsilon [/mm] ist doch ein Terminalsymbol, dann könnte man doch die 3. regel auch aus der 2. ableiten oder?
oder ist S gar kein Nicht-Terminalsymbol und wird als weiteres Sondersymbol betrachtet?
wäre nett, wenn hier jemand klarheit schaffen könnte.
Gruß Ari
|
|
| |
|
- mann muss das leere wort mit angeben da es sonst eine andere Grammatik wäre die eine andere sprache erzeugt als mit dem leeren Wort!
- S ist ein NT!
Mehr kann ich dazu auch nicht sagen weil ich die grammatik bissle sinnlos find?!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 13:28 Di 09.01.2007 | | Autor: | AriR |
ich stütze mich hier auf diesen artikel:
http://de.wikipedia.org/wiki/Chomsky-Normalform
|
|
|
| |
|
Hallo Ari,
man sollte stets unterscheiden zwischen der leeren Menge (als Sprache) und einer (damit dann nicht-leeren) Menge,
die den leeren String [mm] \epsilon [/mm] enthält, also den String der Länge 0.
Es ist halt allgemein [mm] \emptyset\neq \{emptyset\}, [/mm] nicht wahr ?
Gruß,
Mathias
|
|
|
|
