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.

Een stapelautomaat

Formele DefinitieBewerken

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.

VoorbeeldBewerken

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  .