Kontextfreie Grammatik: Unterschied zwischen den Versionen

Aus SibiWiki
Zur Navigation springen Zur Suche springen
 
(2 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=
=Fachbegriffe=
Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache
Nicht-terminal-symbole, Terminal-Symbole, Startsymbol, Produktionsregeln, Ableitung (eines Wortes), Sprache


Zeile 37: Zeile 38:


=Zusammenhang zum Kellerautomat=
=Zusammenhang zum Kellerautomat=
Jede kontextfreie Sprache lässt sich durch einen nicht-deterministischen [[Kellerautomat]] überprüfen.
 
* 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...

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.