Kontextfreie Grammatik: Unterschied zwischen den Versionen
(Die Seite wurde neu angelegt: „Kategorie:endliche Automaten Kategorie:Informatik-Q2 Kategorie:Informatik-Abitur Kategorie:Informatik =Definition= Eine '''Grammatik''' G wird…“) |
|||
| (3 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 3: | Zeile 3: | ||
[[Kategorie:Informatik-Abitur]] | [[Kategorie:Informatik-Abitur]] | ||
[[Kategorie:Informatik]] | [[Kategorie:Informatik]] | ||
<font color='red'>'''nur relevant für den Leistungskurs!'''</font> | |||
=Fachbegriffe= | |||
Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache | |||
=Definition= | =Definition= | ||
| Zeile 34: | Zeile 38: | ||
=Zusammenhang zum Kellerautomat= | =Zusammenhang zum Kellerautomat= | ||
Jede | |||
* Jede von einer kontextfreien Grammatik erzeugte Sprache lässt sich durch einen <u>nicht-deterministischen</u> [[Kellerautomat]] überprüfen. | |||
* 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... | |||
** 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:''' | |||
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]] | |||
=Grenzen der kontextfreien Sprache= | =Grenzen der kontextfreien Sprache= | ||
Die Sprache L = {a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>} ist nicht kontextfrei. | Die Sprache L = {a<sup>n</sup>b<sup>n</sup>c<sup>n</sup>} ist nicht kontextfrei. | ||
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.