Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
Autor |
Nachricht |
Pete
Anmeldungsdatum: 24.11.2005 Beiträge: 3
|
Verfasst am: 24. Nov 2005 13:27 Titel: Kontextfreie Grammatik |
|
|
Ich hab ein Problem, über das ich mir schon den ganzen Mittag den Kopf zerbreche, aber noch auf keine vernünftige Lösung gekommen bin, vielleicht hat ja jemand ne Idee:
L2 = { w e { 0, 1 } * | w enthält die Teilfolge 00 nicht }
die entsprechende Grammatik darf nur 4 Produktionen haben |
|
Nach oben |
|
|
|
kurellajunior Administrator
Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow
|
Verfasst am: 24. Nov 2005 13:37 Titel: |
|
|
Wo ist das Problem? Die Grammatik muss lediglich 00 bei den nicht Terminalen besitzen und in alle Möglichkeiten auflösen.
s->0
s->0s
00->1
00->0
mmh, dat is nicht Kontextfrei, verstehe das Problem. *Weitergrübel*
Jan _________________
|
|
Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005 Beiträge: 149
|
Verfasst am: 24. Nov 2005 15:04 Titel: |
|
|
S -> 1S | 01S | 0 | Eps
Ließe sich mittels vollständiger Induktion über den Ableitungsstrang verifizieren.
Es lässt sich aber einfach nachvollziehen wenn man die Regeln beachtet:
1.) Man kann soviele 1-en hintereinanderreihen wie man lustig ist
2.) Wenn man eine 0 schreibt, dann muss danach entweder eine 1 oder nichtsmehr kommen. |
|
Nach oben |
|
|
Pete
Anmeldungsdatum: 24.11.2005 Beiträge: 3
|
Verfasst am: 24. Nov 2005 15:34 Titel: |
|
|
Ja,
du hast recht.
Danke nochmal |
|
Nach oben |
|
|
kurellajunior Administrator
Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow
|
Verfasst am: 24. Nov 2005 23:10 Titel: |
|
|
Tobias hat Folgendes geschrieben: | S -> 1S | 01S | 0 | Eps
Ließe sich mittels vollständiger Induktion über den Ableitungsstrang verifizieren.
|
Die sit schön, aber unter Berücksichtigung der Überschrift, nicht tauglich, da nicht Kontextfrei...
Hab aber auch keine wirklich gute Idee
Jan _________________
|
|
Nach oben |
|
|
Tobias
Anmeldungsdatum: 15.02.2005 Beiträge: 149
|
Verfasst am: 25. Nov 2005 01:03 Titel: |
|
|
Türlich ist das kontextfrei.
Eine Grammatik ist kontextfrei, wenn nur Nichtterminale auf Satzformen abgeleitet werden. |
|
Nach oben |
|
|
kurellajunior Administrator
Anmeldungsdatum: 14.02.2005 Beiträge: 214 Wohnort: Berlin-Pankow
|
Verfasst am: 25. Nov 2005 13:19 Titel: |
|
|
*Ups*
Hatte eine andere Bedingung im Kopf. Mmh, alles klar
Jan _________________
|
|
Nach oben |
|
|
|