Kontextfreie Grammatik: Unterschied zwischen den Versionen
| Zeile 42: | Zeile 42: | ||
* Zu jeder von einem <u>nicht-deterministischen</u> [[Kellerautomat]] erkannten Sprache gibt es eine kontextfreie Grammatik. | * Zu jeder von einem <u>nicht-deterministischen</u> [[Kellerautomat]] erkannten Sprache gibt es eine kontextfreie Grammatik. | ||
''Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet. <br/>Irgendetwas muss ja auch für das Studium noch übrig bleiben... | ''Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet. <br/>Irgendetwas muss ja auch für das Studium noch übrig bleiben... | ||
** Wer sich den (langatmigen!!) Beweis mal anschauen will: <br/>[https://ai.dmi.unibas.ch/_files/teaching/fs14/theo/slides/theo10.pdf Theorie der Informatik, Kontextfreie Sprachen II, Universität Basel 2014]<br/>S. 17 ff. | |||
'''Zu beachten ist:''' | '''Zu beachten ist:''' | ||
Der nicht-deterministische Kellerautomat ist '''mächtiger''' als der deterministische Kellerautomat!<br/>D.h. es gibt Sprachen, die von einem Nicht-Deterministischen Kellerautomaten geprüft werden können, nicht aber von einem Deterministischen Kellerautomaten. | Der nicht-deterministische Kellerautomat ist '''mächtiger''' als der deterministische Kellerautomat!<br/>D.h. es gibt Sprachen, die von einem Nicht-Deterministischen Kellerautomaten geprüft werden können, nicht aber von einem Deterministischen Kellerautomaten. | ||
Vgl. [[Kellerautomat]] | Vgl. [[Kellerautomat]] | ||
Aktuelle Version vom 5. November 2023, 10:39 Uhr
nur relevant für den Leistungskurs!
Fachbegriffe
Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache
Definition
Eine Grammatik G wird durch ein 4-Tupel (N, T, S, P) definiert:
- N ist die Menge der Nichtterminalsymbole.
- T ist die Menge der Terminalsymbole.
- S ∈ N ist das Startsymbol.
- P ist die Menge der Produktionsregeln.
Eine kontextfreie Grammatik ist eine Grammatik, bei der alle Produktionen den folgenden Anforderungen genügen:
- links darf nur ein Nichtterminal stehen.
- rechts darf eine (endliche) Kombination von Terminal- und Nichtterminal-Symbolen stehen.
Somit ist klar, dass jede reguläre Grammatik auch eine kontextfreie Grammatik ist.
Beispiel
Die Sprache L = {anbn} lässt sich mit einer kontextfreien Grammatik erzeugen:
- G= (N, T, S, P)
- Nichtterminalsymbole N = {S}
- Terminalsymbole T = {a,b}
- Startsymbol S = S
- Produktionsregeln P = {
- S → aSb | ε
- }
Beispiel für die Ableitung eines Wortes
Dass das Wort "aabb" zur Sprache L gehört, lässt sich durch folgende Ableitung zeigen:
- S → aSb → aaSbb → aabb
Bei der letzten Ableitung wurde das S durch nichts (ε) ersetzt.
Zusammenhang zum Kellerautomat
- Jede von einer kontextfreien Grammatik erzeugte Sprache lässt sich durch einen nicht-deterministischen Kellerautomat überprüfen.
- Zu jeder von einem nicht-deterministischen Kellerautomat erkannten Sprache gibt es eine kontextfreie Grammatik.
Die Frage nach dem "Warum?" geht auch über den Informatik-LK hinaus und bleibt hier unbeantwortet.
Irgendetwas muss ja auch für das Studium noch übrig bleiben...
- Wer sich den (langatmigen!!) Beweis mal anschauen will:
Theorie der Informatik, Kontextfreie Sprachen II, Universität Basel 2014
S. 17 ff.
- Wer sich den (langatmigen!!) Beweis mal anschauen will:
Zu beachten ist:
Der nicht-deterministische Kellerautomat ist mächtiger als der deterministische Kellerautomat!
D.h. es gibt Sprachen, die von einem Nicht-Deterministischen Kellerautomaten geprüft werden können, nicht aber von einem Deterministischen Kellerautomaten.
Vgl. Kellerautomat
Grenzen der kontextfreien Sprache
Die Sprache L = {anbncn} ist nicht kontextfrei.