Stapelautomaat

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een 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[bewerken]

Formeel is een PDA een automaat met

met

een eindige verzameling toestanden
een eindige verzameling symbolen, het alfabet van de automaat (of taal) 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 ;
  • .

Voorbeeld[bewerken]

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 .