Normale Automaten haben trotz ihrer Mächtigkeit so ihre Grenzen. Es ist beispielsweise für den allgemeinen Fall nicht möglich, einen Automaten zu basteln, der überprüft, ob ein String aus gleich vielen 0 wie 1 besteht. Dies deshalb, da sie keinerlei Möglichkeit besitzen, irgendwelche Informationen, die nicht mit dem aktuellen State zu tun haben, zu speichern. Damit ist gemeint, dass ein Automat zwar sehr wohl weiss, in welchem State er sich befindet und welchen Weg er bei welchem Eingangssignal nehmen muss, er momentan jedoch nicht sagen kann, wie das beim nächsten aussehen wird oder wieviele States er insgesamt bereits besucht hat, oder ähnliches.

Dies wird nun entschärft durch externen Speicher. Ab jetzt haben Automaten die Möglichkeit, einen oder mehrere Lese/Schreibköpfe zu dirigieren, die auf endlichem oder unendlichem Speicherplatz Daten ablegen und herauslesen können. Zur Verallgemeinerung wird stets angenommen, dass eine Speicherzelle eine beliebig grosse Zahl speichern kann (was natürlich in der wirklichen Welt absoluter Humbug ist).

Counter

Ein Counter ist die einfachste Form eines Automaten mit externem Speicher. Er besitzt genau eine Speicherzelle. Da in solchen Speicherzellen verallgemeinert gesehen Zahlen gespeichert werden, liegt es nahe, die drei wichtigsten Funktionen folgendermassen festzulegen: Der Automat kann der Speicherzelle befehlen, 1 dazuzuzählen (INC), 1 abzuzählen (DEC) und überprüfen, ob die Zelle 0 ist. INC und DEC sind dabei Aktionen, die der Automat während eines Übergangs ausführen kann. Das Resultat der 0-Überprüfung jedoch fliesst als ein weiteres Eingangssignal in den Automaten ein (entweder "is0" oder "not0").

Hier ein einfaches Beispiel eines Automaten, der überprüft, ob ein String gleich viele 0 wie 1 enthält (Start bei 0):

      (0,-) / INC
      (1,-) / DEC
#####------------->#===#<--\  (0,-) / INC
# 0 #              | 1 |   |  (1,-) / DEC
#####<-------------#===#---/
      (e,is0) / -

Bei den Übergängen wird nun links des Slashs / geschrieben, was für Eingangssignale überprüft werden (0 oder 1 kommen vom einzulesenden String und is0 kommt von der 0-Überprüfung). Rechts davon steht die Aktion, die der Automat aufgrund dieser Signal-Belegung ausführen soll. Der Strich - bedeutet hierbei für das Überprüfungssignal, dass es egal ist, ob is0 oder not0. Für die Aktion bedeutet es: führe keine Aktion aus.

Dieses einleitende Beispiel ist eigentlich bereits alles, was so ein Counter kann. Es ist beispielsweise nicht möglich, zwei Zahlen in einer zu codieren (sowas wie Primzahlenzerlegung 2^a*3^b) und so bleibt der Nutzen dieser Counter bei dem, was sie eben darstellen: es sind einfache Zähler.

deterministic und non-deterministic Pushdown automata, Stack-Automaten

Ein pushdown automata hat nicht nur eine Speicherstelle, sondern unendlich viele. Allerdings kann er auf diese Speicherstellen nicht beliebig zugreifen, er benutzt den Speicher als Stack. Er kennt dabei die Aktionen PUSH und POP und hat die beiden Signale TOP und (zur Vervollständigung) EMPTYSTACK (hier kurz MT). PUSH legt das gelesene Zeichen an die nächste freie Stelle auf dem Stack, POP löscht diese Stelle und verringert den Stack wieder um 1. TOP gibt das Zeichen zurück, das an der momentanen Stelle des Stacks liegt und MT ergibt 1, wenn der Stack leer ist.

Bei den Stack-Automaten gibt es keine Aequivalenz zwischen deterministisch und nicht-deterministisch. Ein nicht-deterministischer PDA ist mächtiger als ein deterministischer. Hier das Beispiel des Palindroms: Der deterministische Ansatz (oben) benötigt einen Marker c in der Mitte des zu überprüfenden Strings, der nicht-deterministische braucht sowas nicht, er wechselt spontan in den rechten State (Zur Erinnerung: beim nicht-deterministischen Automaten kommt es nur darauf an, ob mindestens eine Möglichkeit besteht, dass der Automat am Ende des Eingabestrings in einem Akzeptor landet) (Start bei L).

(0,-) / PUSH /-->#===#  (c,-) / -  #===#<--\ (0,0) / POP
(1,-) / PUSH |   | L |------------>| R |   | (1,1) / PUSH
             \---#===#             #===#---/
                          #####      |
                          # E #<-----/MT=1
                          #####

(0,-) / PUSH /-->#===#  (e,-) / -  #===#<--\ (0,0) / POP
(1,-) / PUSH |   | L |------------>| R |   | (1,1) / PUSH
             \---#===#             #===#---/
                         #####      |
                         # E #<-----/MT=1
                         #####

Zusätzlich muss noch bemerkt werden, dass PDAs (egal ob deterministisch oder nicht) trotz der unendlichen Speicherkapazität nicht sämtliche Probleme lösen können. Dies aufgrund der Stack-Bauweise des Speichers. So können zwar beliebig viele Informationen gespeichert werden, allerdings können frühere Informationen nicht erreicht werden, ohne dass die neueren verloren gehen. Beispielsweise ist es nicht möglich, zu überprüfen, ob ein String aus zwei gleichen Teilstrings zusammengesetzt ist.

linear bounded automata, Automaten mit begrenztem ramdom-access-Memory

Bei diesem Typ lohnt es sich, den Begriff des Tapes einzuführen. Bisher wurde stets angenommen, der zu überprüfende String komme einfach so irgendwie in den Automaten hinein. Ab jetzt sei er jedoch auf einem Tape, einem Bandlaufwerk, gespeichert. Bis anhin wurde von diesem Bandlaufwerk einfach von vorne bis hinten schön immer ein Zeichen nach dem anderen ausgelesen. Ab jetzt ist es jedoch möglich, den Lese-/Schreibkopf dieses Bandlaufwerkes ebenfalls zu dirigieren und sowohl vom Laufwerk zu lesen, als auch Daten zu schreiben (Das Bandlaufwerk ersetzt somit auch gleich den Speicher). Zusätzlich hat ein LBA auch die Möglichkeit, neue Zeichen ausserhalb des Alphabets (die aber festgelegt sein müssen) zu benutzen. Das Bandlaufwerk kann aber nicht über seine Grenzen (welche durch den Eingabestring gegeben sind) hinausbewegt werden.

Die Aktionen eines LBA sind L: eine Speicherzelle nach links gehen, R: eine nach rechts, Wx: Das Zeichen x an der momentanen Stelle speichern, H: den Automaten Stoppen. Das einzige Eingangssignal ist jetzt das Lesen der aktuellen Speicherzelle.