Sprachakzeptanz von Kellerautomaten

Sprachakzeptanz von Kellerautomaten

Nichtdeterministische Kellerautomaten können die Typ-2-Sprachen der Chomsky-Hiearchie erkennen. Nichtdeterministische Kellerautomaten erkennen also die kontextfreien Sprachen.