next up previous
Next: Applet Up: Arbeitsweise Previous: Akzeptierte Sprachen

deterministische und nichtdet. Kellerautomaten

Ein nichtdeterministischer Kellerautomat akzeptiert mehr als ein det. KA. Es gilt \( DKA\subset NKA \).

Beispiel: Die Menge aller Palindrome \( L=\{w\overline{w}\vert w\in (0+1)^{*}\} \) wird von keinem DKA akzeptiert (keine Möglichkeit die Mitte des Palindroms zu erraten).


Thomas Rabe
1999-09-23