Information Technology Reference
In-Depth Information
Rule
Comment
Rule
Comment
(
a
)
(
s
,
β
,
;
f
,
)
accept
(
g
)
(
p
,
β
,
a
;
f
,
)
accept
(
b
)
(
s
,
a
,
;
s
,
a
)
push a
(
h
)
(
p
,
β
,
γ
;
f
,
)
accept
(
c
)
(
s
,
b
,
γ
;
r
,
)
reject
(
i
)
(
p
,
a
,
;
r
,
)
reject
(
d
)
(
s
,
b
,
a
;
p
,
)
pop a, enter pop state
(
j
)
(
f
,
,
;
f
,
)
stay in accept state
(
e
)
(
p
,
b
,
a
;
p
,
)
pop a
(
k
)
(
r
,
,
;
r
,
)
stay in reject state
(
f
)
(
p
,
b
,
γ
;
r
,
)
reject
Figure 4.25
Transitions for a PDA that accepts the language
{a
n
b
m
| n ≥ m ≥
0
}
.
EXAMPLE
4.8.2
The PDA
M
=(Σ
,
Γ
,
Q
,
Δ
,
s
,
F
)
,where
Σ=
{a
,
b
,
β}
,
Γ=
{a
,
b
,
γ}
,
Q
=
{
s
,
p
,
r
,
f
}
,
F
=
{
f
}
and
Δ
contains the transitions shown in Fig.
4.25
, accepts the
a
n
b
m
language
L
=
{
|
n
≥
m
≥
0
}
. The state diagram for this machine is shown in Fig.
4.26
.
The rules of Fig.
4.25
work as follows. An empty input in the
stacking state
s
is accepted
(Rule (a)). If a string of
a
's is found, the PDA remains in state
s
and the
a
's a re pushed onto
the stack (Rule (b)). At the first discovery of a
b
in the input while in state
s
,ifthestackis
empty, the input is rejected by entering the
reject state
(Rule (c)). If the stack is not empty,
the
a
at the top is popped and the PDA enters the
pop state
p
(Rule (d)). If while in
p
a
b
is discovered on the input tape when an
a
is found at the top of the stack (Rule(e)), the PDA
pops the
a
and stays in this state because it remains possible that the input contains no more
b
's
than
a
's. On the other hand, if the stack is empty when a
b
is discovered, the PDA enters the
reject state (Rule (f )). If in state
p
the PDA discovers that it has more
a
's than
b
's by read ing
b
,
a
;
p
b
,
γ
;
a
,
;
a
b
,
a
;
β
,
a
;
a
,
;
β
,
γ
;
Start
s
r
b
,
γ
;
β
,
;
,
;
,
;
f
Figure 4.26
The state diagram for the PDA defined by the tables in Fig.
4.25
.
Search WWH ::
Custom Search