Information Technology Reference
In-Depth Information
0, 1
0, 1
q
3
q
R
0
Start
s
0
1
1
q
2
0
Figure 4.21
A minimal-state DFSM equivalent to the DFSM in Fig.
4.14
.
4.8
Pushdown Automata
The pushdown automaton (PDA) has a one-way, read-only, potentially infinite input tape on
which an input string is written (see Fig.
4.22
); its head either advances to the right from the
leftmost cell or remains stationary. It also has a stack, a storage medium analogous to the stack
of trays in a cafeteria. The
stack
is a potentially infinite ordered collection of initially blank
cells with the property that data can be pushed onto it or popped from it. Data is
pushed
onto
the top of the stack by moving all existing entries down one cell and inserting the new element
in the top location. Data is
popped
by removing the top element and moving all other entries
up one cell. The control unit of a pushdown automaton is a finite-state machine. The full
power of the PDA is realized only when its control unit is nondeterministic.
DEFINITION
4.8.1
A
pushdown automaton (PDA)
is a six-tuple
M
=(Σ
,
Γ
,
Q
,
Δ
,
s
,
F
)
,
where
Σ
is the
tape alphabet
containing the blank symbol
β
,
Γ
is the
stack alphabet
containing
the blank symbol
γ
,
Q
is the finite
set of states
,
Δ
))
is the set of
transitions
,
s
is the
initial state
,and
F
is the
set of final states
.Wenowdescribe
transitions.
If for state
p
,tapesymbol
x
,andstacksymbol
y
the transition
(
p
,
x
,
y
;
q
,
z
)
⊆
(
Q
×
(Σ
∪{
}
)
×
(Γ
∪{
}
)
×
Q
×
(Γ
∪{
}
∈
Δ
,thenif
M
is in state
p
,
x
∈
Σ
is under its tape head, and
y
∈
Γ
is at the top of its stack,
M
may pop
y
from
its stack, enter state
q
Γ
onto its stack. However, if
x
=
,
y
=
or
z
=
,
then
M
does not read its tape, pop its stack or push onto its stack, respectively. The head on the tape
either remains stationary if
x
=
or advances one cell to the right if
x
∈
Q
,andpush
z
∈
=
.
If at each point in time a unique transition
(
p
,
x
,
y
;
q
,
z
)
maybeapplied,thePDAis
deter-
ministic
. Otherwise it is
nondeterministic
.
The PDA
M
accepts the input string
w
Σ
∗
if when started in state
s
with an empty
stack (its cells contain the
blank stack symbol
γ
)and
w
placed left-adjusted on its otherwise blank
tape (its blank cells contain the
blank tape symbol
β
), the last state entered by
M
after reading
the components of
w
and no other tape cells is a member of the set
F
.
M
accepts the language
L
(
M
)
consisting of all such strings.
∈
Some of the special cases for the action of the PDA
M
on empty tape or stack sym-
bols are the following:
if
(
p
,
x
,
;
q
,
z
)
,
x
is read, state
q
is entered, and
z
is pushed onto
Search WWH ::
Custom Search