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
Formeel is een PDA een automaat
M
{\displaystyle M}
M
=
(
Q
,
Σ
,
Γ
,
δ
,
q
0
,
F
)
{\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},F)\ }
met
Q
{\displaystyle Q\ }
Σ
{\displaystyle \Sigma \ }
alfabet van de automaat geheten
Γ
{\displaystyle \Gamma \ }
alfabet van de stack
δ
{\displaystyle \,\delta }
Q
×
Σ
ϵ
×
Γ
ϵ
⟶
P
(
Q
×
Γ
ϵ
)
{\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma _{\epsilon }\longrightarrow {\mathcal {P}}(Q\times \Gamma _{\epsilon })}
transitiefunctie
q
0
{\displaystyle q_{0}\ }
begintoestand
F
⊆
Q
{\displaystyle F\subseteq Q}
accepterende toestanden waarbij
Σ
ϵ
=
Σ
∪
{
ϵ
}
{\displaystyle \Sigma _{\epsilon }=\Sigma \cup \{\epsilon \}}
Γ
ϵ
=
Γ
∪
{
ϵ
}
{\displaystyle \Gamma _{\epsilon }=\Gamma \cup \{\epsilon \}}
Een stapelautomaat accepteert een woord w , als w geschreven kan worden als
w
1
w
2
…
w
n
{\displaystyle w_{1}w_{2}\ldots w_{n}}
w
i
∈
Σ
ϵ
{\displaystyle w_{i}\in \Sigma _{\epsilon }}
r
0
,
…
,
r
n
{\displaystyle r_{0},\ldots ,r_{n}}
s
0
,
…
,
s
n
{\displaystyle s_{0},\ldots ,s_{n}}
s
i
∈
Γ
∗
{\displaystyle s_{i}\in \Gamma ^{*}}
r
0
=
q
0
{\displaystyle r_{0}=q_{0}}
s
0
=
ϵ
{\displaystyle s_{0}=\epsilon }
voor alle
0
≤
i
≤
n
−
1
{\displaystyle 0\leq i\leq n-1}
(
r
i
+
1
,
β
)
∈
δ
(
r
i
,
w
i
+
1
,
α
)
{\displaystyle (r_{i+1},\beta )\in \delta (r_{i},w_{i+1},\alpha )}
s
i
=
α
ω
{\displaystyle s_{i}=\alpha \omega }
s
i
+
1
=
β
ω
{\displaystyle s_{i+1}=\beta \omega }
ω
∈
Γ
∗
{\displaystyle \omega \in \Gamma ^{*}}
r
n
∈
F
{\displaystyle r_{n}\in F}
De taal van een stapelautomaat
M
{\displaystyle M}
L
(
M
)
{\displaystyle L(M)}
M
{\displaystyle M}
De stapelautomaat
M
=
(
{
q
0
,
q
a
,
q
b
,
q
f
}
,
{
a
,
b
}
,
{
S
,
1
}
,
δ
,
q
0
,
{
q
f
}
)
{\displaystyle M=(\{q_{0},q_{a},q_{b},q_{f}\},\{a,b\},\{S,1\},\delta ,q_{0},\{q_{f}\})}
δ
(
q
0
,
a
,
ϵ
)
=
{
(
q
a
,
1
)
}
{\displaystyle \delta (q_{0},a,\epsilon )=\{(q_{a},1)\}}
δ
(
q
a
,
a
,
ϵ
)
=
{
(
q
a
,
1
)
}
{\displaystyle \delta (q_{a},a,\epsilon )=\{(q_{a},1)\}}
δ
(
q
a
,
b
,
1
)
=
{
(
q
b
,
ϵ
)
}
{\displaystyle \delta (q_{a},b,1)=\{(q_{b},\epsilon )\}}
δ
(
q
b
,
b
,
1
)
=
{
(
q
b
,
ϵ
)
,
(
q
f
,
ϵ
)
}
{\displaystyle \delta (q_{b},b,1)=\{(q_{b},\epsilon ),(q_{f},\epsilon )\}}
δ
(
q
,
x
,
y
)
=
∅
{\displaystyle \delta (q,x,y)=\emptyset }
q
∈
Q
{\displaystyle q\in Q}
x
∈
Σ
ϵ
{\displaystyle x\in \Sigma _{\epsilon }}
y
∈
Γ
ϵ
{\displaystyle y\in \Gamma _{\epsilon }}
accepteert de contextvrije taal
{
a
n
b
n
∣
n
≥
1
}
{\displaystyle \{a^{n}b^{n}\mid n\geq 1\}}
Voor het woord
w
=
a
a
b
b
{\displaystyle w=aabb}
r
0
=
q
0
,
s
0
=
ϵ
{\displaystyle r_{0}=q_{0},s_{0}=\epsilon }
r
1
=
q
a
,
s
1
=
1
{\displaystyle r_{1}=q_{a},s_{1}=1}
w
1
=
a
{\displaystyle w_{1}=a}
(
q
a
,
1
)
∈
δ
(
q
0
,
a
,
ϵ
)
{\displaystyle (q_{a},1)\in \delta (q_{0},a,\epsilon )}
r
2
=
q
a
,
s
2
=
11
{\displaystyle r_{2}=q_{a},s_{2}=11}
w
2
=
a
{\displaystyle w_{2}=a}
(
q
a
,
1
)
∈
δ
(
q
a
,
a
,
ϵ
)
{\displaystyle (q_{a},1)\in \delta (q_{a},a,\epsilon )}
r
3
=
q
b
,
s
3
=
1
{\displaystyle r_{3}=q_{b},s_{3}=1}
w
3
=
b
{\displaystyle w_{3}=b}
(
q
b
,
ϵ
)
∈
δ
(
q
a
,
b
,
1
)
{\displaystyle (q_{b},\epsilon )\in \delta (q_{a},b,1)}
r
4
=
q
f
,
s
4
=
ϵ
{\displaystyle r_{4}=q_{f},s_{4}=\epsilon }
w
4
=
b
{\displaystyle w_{4}=b}
(
q
f
,
ϵ
)
∈
δ
(
q
b
,
b
,
1
)
{\displaystyle (q_{f},\epsilon )\in \delta (q_{b},b,1)}
het woord wordt geaccepteerd omdat
q
f
∈
F
{\displaystyle 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
