Zum neuen Informatik-Forum >>
 FAQFAQ   SuchenSuchen   MitgliederlisteMitgliederliste   BenutzergruppenBenutzergruppen   RegistrierenRegistrieren   ProfilProfil   Einloggen, um private Nachrichten zu lesenEinloggen, um private Nachrichten zu lesen   LoginLogin 

Kontextfreie Grammatik

 
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik
Vorheriges Thema anzeigen :: Nächstes Thema anzeigen  
Autor Nachricht
Pete



Anmeldungsdatum: 24.11.2005
Beiträge: 3

BeitragVerfasst am: 24. Nov 2005 13:27    Titel: Kontextfreie Grammatik Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
kurellajunior
Administrator


Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow

BeitragVerfasst am: 24. Nov 2005 13:37    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Tobias



Anmeldungsdatum: 15.02.2005
Beiträge: 149

BeitragVerfasst am: 24. Nov 2005 15:04    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden
Pete



Anmeldungsdatum: 24.11.2005
Beiträge: 3

BeitragVerfasst am: 24. Nov 2005 15:34    Titel: Antworten mit Zitat

Ja,

du hast recht.

Danke nochmal
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
kurellajunior
Administrator


Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow

BeitragVerfasst am: 24. Nov 2005 23:10    Titel: Antworten mit Zitat

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
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Tobias



Anmeldungsdatum: 15.02.2005
Beiträge: 149

BeitragVerfasst am: 25. Nov 2005 01:03    Titel: Antworten mit Zitat

Türlich ist das kontextfrei.

Eine Grammatik ist kontextfrei, wenn nur Nichtterminale auf Satzformen abgeleitet werden.
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden
kurellajunior
Administrator


Anmeldungsdatum: 14.02.2005
Beiträge: 214
Wohnort: Berlin-Pankow

BeitragVerfasst am: 25. Nov 2005 13:19    Titel: Antworten mit Zitat

*Ups*

Hatte eine andere Bedingung im Kopf. Mmh, alles klar Wink

Jan

_________________
Nach oben
Benutzer-Profile anzeigen Private Nachricht senden Website dieses Benutzers besuchen
Beiträge der letzten Zeit anzeigen:   
Dieses Forum ist gesperrt, du kannst keine Beiträge editieren, schreiben oder beantworten.   Dieses Thema ist gesperrt, du kannst keine Beiträge editieren oder beantworten.    Informatikerboard.de Foren-Übersicht -> Theoretische Informatik Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum nicht posten
Du kannst Dateien in diesem Forum nicht herunterladen