Solu tion
The PDA that will accept {
|
}
a b n
n
n
2
1
≥ is given by
PDA = ({q 0 , q 1 , q 2 }, {a, b}, {a, z 0 }, δ, q 0 , z 0 , φ)
where δ is given by
δ ( , , )
{( ,
)}
q a z
q a z
0
0
1
0
=
δ ( , , )
{( ,
)}
q a a
q a a
1
1
=
δ ( , , )
{( , )}
q b a
q a
1
2
=
δ
λ
( , , )
{( , )}
q b a
q
2
1
=
δ
λ
λ
( , , )
{( , )}
q
z
q
1
0
1
=
Ì Exam ple 3.1.3: Obtain the PDA accepting {
| ,
}
a b c m n
m m n
≥1 by
empty store.
Solu tion
The PDA which will accept {
| ,
}
a b c m n
m m n
≥1 by empty store is given below.
PDA = ({ , }, ( , , }, { , }, , , , )
q q
a b c
z z
q z
0
1
0 1
0
0
δ
φ
where δ is given by
δ ( , , )
{( , , )}
q a z
q z z
0
0
0
0
=
δ ( , , )
{( ,
)}
q a z
q z z
0
1
0
1 1
=
δ
λ
( , , )
{( , )}
q b z
q
0
1
1
=
δ
λ
( , , )
{( , )}
q b z
q
1
1
1
=
δ ( , , )
{( , )}
q c z
q z
1
0
1
0
=
δ
λ
λ
( , , )
{( , )}
q
z
q
1
0
1
=
When an ‘a’ is read z 1 is added. When a ‘b’ is read then z 1 is removed.
Ì Exam ple 3.1.4: Construct a PDA accepting {
| ,
}
a b a m n
n m
n
≥1 by
final state.
Solu tion
THEOREM: If A Q
q z F
= ( , , , , , , )
Σ Γ δ 0 0
is a PDA accepting L by null store,
we can find a PDA
B Q
q z F
B
= ′
′
′ ′ ′
( , , , , , , )
Σ Γ δ
0
0
which accept L by final state, i.e.,
L = N(A) = T(B).
Using the above theorem, we have
B
q q q q
a b a z z
q z q
f
f
=
′
′
′ ′
({ , , , }, { , }, { , , }, , , , { })
0
1
0
0
0
0
0
δ
where δ is given by
δ
λ
( , , )
{( ,
)}
′
′ =
′
q
z
q z z
0
0
0
0 0
Pushdown Automata
165