Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

EBNF
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> EBNF
 
Autor Nachricht
calippo
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 17.01.2009
Beiträge: 29

BeitragVerfasst am: 27 Jan 2009 - 16:01:10    Titel: EBNF

hallo an alle,

ich habe da eine frage bezüglich EBNF.

wenn ich eine EBNF-Grammatik G mit einem Startsymbol S habe also etwa so:

Y= 'x' | 'y' | 'z' | '1' | '2'
X={ Y 'y' }
S= [Y] 'x' X {'z'}

wie überprüfe ich nun ob die wörter:
1)yxyy
2)yxyyzy
3)x2
4)1xxyz

in der von G erzeugten Sprache enthalten ist oder nicht?
Annihilator
Valued Contributor
Benutzer-Profile anzeigen
Valued Contributor


Anmeldungsdatum: 18.05.2007
Beiträge: 6394
Wohnort: (hier nicht mehr aktiv)

BeitragVerfasst am: 27 Jan 2009 - 16:36:01    Titel:

Man kann das deterministisch machen, aber das wird etwas umfangreicher. "Besser" ist hier das nicht-deterministische menschliche "scharfe Hinsehen".

Das einzelne 'x', welches in der Konklusion der Produktion mit der syntaktischen Variable S als Prämisse vorkommt, kann da beispielsweise ganz hilfreich sein:

    Falls kein 'x' im Wort vorkommt, so kann es auch nicht Element der von G erzeugten Sprache sein.

    Falls nur ein einziges 'x' im Wort enthalten ist, so muss es jenes, aus der angesprochenen Konklusion sein.

    Wenn ein Wort nicht mit 'x' beginnt, so muss die syntaktische Variable Y am Anfang zum Einsatz gekommen sein (die eckigen Klammern stehen ja für Optionen).

    Ein Wort, welches Element der von G erzeugten Sprache ist, endet mit 'y' und einer beliebigen Anzahl an 'z' (die geschweiften Klammern stehen ja für beliebige Wiederholdung)


Damit fallen schon mal 2) und 3) raus. Bei den übrigen reicht es eine Ableitungs-Folge anzugeben:

S
|-- [Y] 'x' X {'z'}
|-- 'y' 'x' X {'z'}
|-- 'y' 'x' {Y 'y'} {'z'}
|-- 'y' 'x' {'y' 'y'} {'z'}
|-- 'y' 'x' 'y' 'y' {'z'}
|-- 'y' 'x' 'y' 'y'

Daher ist yxyy offensichtlich Element von L(G). Versuch's mal mit der 4) !
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> EBNF
Neues Thema eröffnen   Neue Antwort erstellen 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.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum