Stapelautomaat
Een stapelautomaat, ofwel een push-down-automaat (PDA), is een eindige automaat die gebruikmaakt van een stack. De klasse van formele talen die door stapelautomaten wordt geaccepteerd, is de klasse van contextvrije talen. Dat wil zeggen dat stapelautomaten even krachtig zijn als contextvrije grammatica's.

Formele Definitie 
Formeel is een PDA een automaat  met

met
 een eindige verzameling toestanden
 een eindige verzameling symbolen, het alfabet van de automaat geheten
 een eindige verzameling symbolen, het alfabet van de stack
:  een transitiefunctie
 de begintoestand
 de verzameling accepterende toestanden
waarbij  en .

Een stapelautomaat accepteert een woord w, als w geschreven kan worden als , waarbij , als er een rij  van toestanden en een rij  van stapelinhouden () zijn, zo dat
  en ;
 voor alle  geldt: , waarbij  en  voor een ;
 .
De taal van een stapelautomaat , genoteerd als , is de verzameling van alle woorden die door  geaccepteerd worden.

Voorbeeld 
De stapelautomaat  met
 
 
 
 
  voor alle andere combinaties van ,  en 
accepteert de contextvrije taal .

Voor het woord  hebben we bijvoorbeeld:
 
  (want  en )
  (want  en )
  (want  en )
  (want  en )
 het woord wordt geaccepteerd omdat .

Systeemtheorie
Theoretische informatica