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 gebruik maakt 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 M met

M = ( Q, \Sigma , \Gamma , \delta , q_0 , F ) \

met

Q \ een eindige verzameling toestanden
\Sigma \ een eindige verzameling symbolen, het alfabet van de automaat (of taal) geheten
\Gamma \ een eindige verzameling symbolen, het alfabet van de stack
\,\delta: Q \times \Sigma_{\epsilon} \times \Gamma_{\epsilon} \longrightarrow \mathcal{P}( Q \times \Gamma_{\epsilon}) een transitiefunctie
q_0 \ de begintoestand
F \subseteq Q de verzameling accepterende toestanden

waarbij \Sigma_\epsilon=\Sigma\cup\{\epsilon\} en \Gamma_\epsilon=\Gamma\cup\{\epsilon\}.

Een stapelautomaat accepteert een woord w als w geschreven kan worden als w_1w_2\ldots w_n, waarbij w_i\in\Sigma_\epsilon, als er een rij r_0,\ldots,r_n van toestanden en een rij s_0,\ldots,s_n van stapelinhouden (s_i\in\Gamma^*) zijn, zo dat

  • r_0 = q_0 en s_0=\epsilon;
  • voor alle 0 \leq i \leq n-1 geldt: (r_{i+1},\beta) \in \delta(r_i,w_{i+1},\alpha), waarbij s_i=\alpha\omega en s_{i+1}=\beta\omega voor een \omega\in\Gamma^*;
  • r_n\in F.

Voorbeeld[bewerken]

De stapelautomaat M = (\{q_0,q_a,q_b,q_f\},\{a,b\},\{S,1\},\delta,q_0,\{q_f\}) met

  • \delta(q_0,a,\epsilon) = \{(q_a,1)\}
  • \delta(q_a,a,\epsilon) = \{(q_a,1)\}
  • \delta(q_a,b,1) = \{(q_b,\epsilon)\}
  • \delta(q_b,b,1) = \{(q_b,\epsilon),(q_f,\epsilon)\}
  • \delta(q,x,y) = \emptyset voor alle andere combinaties van q\in Q, x\in\Sigma_\epsilon en y\in\Gamma_\epsilon

accepteert de contextvrije taal \{a^nb^n \mid n \geq 1\}.

Voor het woord w = aabb hebben we bijvoorbeeld:

  • r_0 = q_0, s_0 = \epsilon
  • r_1 = q_a, s_1 = 1 (want w_1=a en (q_a,1)\in\delta(q_0,a,\epsilon))
  • r_2 = q_a, s_2 = 11 (want w_2=a en (q_a,1)\in\delta(q_a,a,\epsilon))
  • r_3 = q_b, s_3 = 1 (want w_3=b en (q_b,\epsilon)\in\delta(q_a,b,1))
  • r_4 = q_f, s_4 = \epsilon (want w_4=b en (q_f,\epsilon)\in\delta(q_b,b,1))
  • het woord wordt geaccepteerd omdat q_f\in F.
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