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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Pushdown-overview.svg/340px-Pushdown-overview.svg.png)
Formele Definitie
bewerkenFormeel 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
bewerkenDe 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
.
Bronnen, noten en/of referenties
- (en) Michael Sipser, Introduction to the Theory of Computation, Second edition, Internation edition, Cengage Learning, 2006, ISBN 978-0-619-21764-8
🔥 Top keywords: HoofdpaginaEuropees kampioenschap voetbal 2024Speciaal:ZoekenMicky van de VenDonyell MalenMarko ArnautovićOlympiastadion (Berlijn)Europees kampioenschap voetbal mannenMemphis DepayBart Verbruggen (voetballer)Julian AssangeVirgil van DijkXavi SimonsNederlands voetbalelftal (mannen)Cody GakpoWout WeghorstJerdy SchoutenRonald KoemanTijjani ReijndersJoey VeermanLutsharel GeertruidaGevlekte scheerlingEuropees kampioenschap voetbal 2024 (kwalificatie)Marjolein Faber-van de KlashorstEuropees kampioenschap voetbal 1988ChatGPTNederland op het Europees kampioenschap voetbal 1988IShowSpeedDanny MakkelieRafael van der VaartEuropees kampioenschap voetbal 2020Marcel SabitzerOmvolkingPierre van HooijdonkChristoph BaumgartnerNoordelijke MarianenSaipanSpeciaal:RecenteWijzigingenSlovenië