Der folgende Stackautomat N  = (Z, E, H, d, q, F) erkennt die Sprache { aⁿbⁿ  |  n ∈ ℕ }.

Eingabeband

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Stack

Eingabewort

   

 

s	e	h	h'	s'
0	ε	ε	$	1
1	a	ε	a	1
1	b	a	ε	2
2	b	a	ε	2
2	ε	$	ε	3*

Der Stackautomat legt zunächst das Zeichen $ auf den Stack, um dessen unteres Ende zu kennzeichnen. Danach legt er solange jedes gelesene a auf den Stack, bis er auf das erste b stößt. Für jedes gelesene b entfernt er von nun an ein a vom Stack. Wenn er das Zeichen $ im Stack vorfindet, geht er in den Endzustand 3 über.

In dieser Situation ist kein weiterer Zustandsübergang mehr möglich. Falls das Eingabewort w nun vollständig gelesen ist, erkennt der Stackautomat das Wort w.

Dieser Stackautomat ist sogar deterministisch, denn es gibt in jeder Situation nur höchstens einen möglichen Zustandsübergang.