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.