Information Technology Reference
In-Depth Information
a
,
a
;
b
,
b
;
p
β
,
b
;
a
,
γ
;
a
,
b
;
a
,
;
a
c
,
;
b
,
γ
;
b
,
a
;
β
,
a
;
c
,
;
β
,
γ
;
Start
s
r
β
,
;
b
,
;
b
,
;
f
,
;
Figure 4.23
State diagram for the pushdown automaton of Fig.
4.24
which accepts
R
{
w
c
w
}
.
An edge label
a
,
b
;
c
between states
p
and
q
corresponds to the transition
(
p
,
a
,
b
;
q
,
c
)
.
instance of letter
c
while in state
s
,itentersthe
possible accept state
p
(Rule (c)) but enters
the
reject state
r
if it encounters a blank on the input tape (Rule (d)). While in state
p
it
pops an
a
or
b
that matches the same letter on the input tape (Rules (e) and (f )). If the PDA
discovers blank tape and stack symbols, it has identified a palindrome and enters the
accept
state
f
(Rule (g)). On the other hand, if while in state
p
thetapesymbolandthesymbolon
the top of the stack are different or the letter
c
is encountered, the PDA enters the reject state
r
(Rules (h)-(n)). Finally, the PDA does not exit from either the reject or accept states (Rules
(o) and (p)).
Rule
Comment
Rule
Comment
(
a
)
(
s
,
a
,
;
s
,
a
)
push
a
(
i
)
(
p
,
b
,
a
;
r
,
)
reject
(
b
)
(
s
,
b
,
;
s
,
b
)
push
b
(
j
)
(
p
,
β
,
a
;
r
,
)
reject
(
c
)
(
s
,
c
,
;
p
,
)
(
k
)
(
p
,
β
,
b
;
r
,
)
accept?
reject
(
d
)
(
s
,
β
,
;
r
,
)
(
l
)
(
p
,
a
,
γ
;
r
,
)
reject
reject
(
e
)
(
p
,
a
,
a
;
p
,
)
(
m
)
(
p
,
b
,
γ
;
r
,
)
accept?
reject
(
f
)
(
p
,
b
,
b
;
p
,
)
(
n
)
(
p
,
c
,
;
r
,
)
accept?
reject
(
g
)
(
p
,
β
,
γ
;
f
,
)
(
o
)
(
r
,
,
;
r
,
)
accept
stay in reject state
(
h
)
(
p
,
a
,
b
;
r
,
)
(
p
)
(
f
,
,
;
f
,
)
reject
stay in accept state
Figure 4.24
Transitions for the PDA described by the state diagram of Fig.
4.23
.
Search WWH ::
Custom Search