Kontextfreie Grammatik |
24.03.2007, 19:05 | Auf diesen Beitrag antworten » |
Gisa | Kontextfreie Grammatik Hallo Forum, ich habe versucht mir das Kapitel kontextfreie Grammatik durchzulesen aber vergebens :-(. Ich wollte herausfinden was eine kontextfreie Grammatik ist und was nicht. Was ist der Unterschied zu einer regulären Sprache? Häufig begegne ich: E->T | E+T, T->F|T*F, F->a|(F) Sie wären besonders nützlich um geklammerte Sprachstrukturen zu beschreiben. Hmmm. Wäre super wenn ich etwas mehr dazu erfahren könnte. Viele Grüße Gisa |
|
|
25.03.2007, 18:19 | Auf diesen Beitrag antworten » |
Tobias | Kontextfreie Grammatiken erzeugen kontextfreie Sprachen, die von einem nichtdeterministischen Kellerautomat erkannt werden können. Sie sind sozusagen eine Oberklasse der regulären Sprachen, die von deterministischen, endlichen Automaten erkannt werden. Die Sprachhierarchie ist die sog. "Chomsky-Hierarchie". Hier erfährst du mehr: http://de.wikipedia.org/wiki/Kontextfreie_Grammatik http://de.wikipedia.org/wiki/Regul%C3%A4re_Sprache http://de.wikipedia.org/wiki/Chomsky-Hierarchie |
26.03.2007, 17:18 | Auf diesen Beitrag antworten » |
Gisa | Danke für die vielen Quellen :-). ---- Habe ne noch ne Frage bzgl. Pushdown-Automaten. Bei der Aufgabe soll ein Pushdown Automat gezeichnet werden der die Sprache {a^n b^m c^n|m, n>=0} Alphabet {a,b,c} Die ungefähre Lösung lautet: Meine Fragen dazu sind: Wieso ein Automat mit 5 Zuständen? Was bedeutet "[,[->$" Was sagen die anderen Tranisition aus? Könnt ihr mit bitte ein anderes PDA Beispiel samt Lösung zeigen? Wäre für jegliche Hilfe und infos dankbar! Viele Grüße Gisa |
|