Theory: PDA |
Kontextfreie Sprachen |
Kontextfreie Sprachen vom
Sprachtyp 2 der
Chomsky-Hierarchie beinhalten
symmetrische Strukturen, die mittels zentralrekursive Regeln beschrieben
werden. In der kontextfreien Grammatik dürfen Nonterminale durch irgendetwas,
ausser dem Nullelement ersetzt werden.
Beispiel einer kontextfreien
Grammatik:
S -> ab
S -> aSb
Diese Grammatik lässt
die Beschreibung von "centre embedding" zu. Daraus ergibt sich die Sprache
L = {an bn , n >= 0}.
Kontextfreie Sprachen werden
durch nicht-deterministische PDA erkannt.