Information Technology Reference
In-Depth Information
One-way read-only input tape
Stack
Control
Unit
Figure 4.22
The control unit, one-way input tape, and stack of a pushdown automaton.
the stack; if
(
p
,
x
,
y
;
q
,
)
,
x
is read, state
q
is entered, and
y
is popped from the stack;
if
(
p
,
,
y
;
q
,
z
)
,noinputisread,
y
is popped,
z
is pushed and state
q
is entered. Also, if
(
p
,
,
;
q
,
)
,
M
moves from state
p
to
q
without reading input, or pushing or popping the
stack.
Observe that if every transition is of the form
(
p
,
x
,
;
q
,
)
, the PDA ignores the stack and
simulates an FSM. Thus, the languages accepted by PDAs include the regular languages.
We emphasize that a PDA is nondeterministic if for some state
q
,tapesymbol
x
,andtop
stack item
y
there is more than one transition that
M
can make. For example, if
Δ
contains
(
s
,
a
,
;
s
,
a
)
and
(
s
,
a
,
a
;
r
,
)
,
M
has the choice of ignoring or popping the top of the stack
and of moving to state
s
or
r
. If after reading all symbols of
w
M
enters a state in
F
,then
M
accepts
w
.
We now give two examples of PDAs and the languages they accept. The first accepts
palindromes of the form
}
∗
.Thestate
diagram of its control unit is shown in Fig.
4.23
. The second PDA accepts those strings over
{
w
c
w
R
,where
w
R
{
}
is the reverse of
w
and
w
∈{
a
,
b
of the form
a
n
b
m
a
,
b
}
for which
n
≥
m
.
EXAMPLE
4.8.1
The PDA
M
=(Σ
,
Γ
,
Q
,
Δ
,
s
,
F
)
,where
Σ=
{a
,
b
,
c
,
β}
,
Γ=
{a
,
b
,
γ}
,
Q
=
{
s
,
p
,
r
,
f
}
,
F
=
{
f
}
and
Δ
contains the transitions shown in Fig.
4.24
, accepts the
w
c
w
R
language
L
=
{
}
.
The PDA
M
of Figs.
4.23
and
4.24
remains in the
stacking state
s
while encountering
a
's and
b
's on the input tape, pushing these letters (the order of these letters on the stack is the
reverse of their order on the input tape) onto the stack (Rules (a) and (b)). If it encounters an
Search WWH ::
Custom Search