δ
λ
λ
δ
λ
( , , ) {( , )}
( , , )
q
z
q
q
z
f
0
0
0
0
′ =
=
′
δ
λ
λ
δ
λ
( , , ) {( , )}
( , , )
q
z
q
q
z
f
1
0
1
0
′ =
=
′
δ ( , , )
{( ,
)}
q a z
q a z
0
0
0
0
=
δ ( , , )
{( , )}
q a a
q aa
0
0
=
δ ( , , )
{( , )}
q b a
q a
0
1
=
δ ( , , )
{( , )}
q b a
q a
1
1
=
δ
λ
( , , )
{( , )}
q a a
q f
1
=
δ
λ
λ
( , , )
{( , )}
q
z
q
1
0
1
=
Ì Exam ple 3.1.5: Given L a b n m
m n
=
<
{
|
}.
Derive (i) a context-free grammar that accepts L
(ii) a PDA accepting L by empty store
(iii) a PDA accepting L by final state.
Solu tion
(i) Given L a b n m
m n
=
<
{
|
}
CFG is given by G
S a b P S
= ({ }, { , }, , ), where productions P are
S
aSb
S
aS
S
a
→
→
→



 
(ii) The PDA that will accept L(G) by empty store is given by
A
q a b S a b
q S
= ({ }, { , }, { , , }, , , , ),
δ
φ
where δ is defined by the rule:
δ
λ
( , , ) {( ,
), ( , ), ( , )}
q
S
q aSb q aS q a
=
δ
δ
λ
( , , )
( , , ) {( , )}
q a a
q b b
q
=
=
(iii) B Q
q z F
B
= ′
′
′ ′ ′
( , , , , , , )
Σ Γ δ
0
0
, where
′ =
′
′ =
′
=
Q
q q q
S a b z F
q
f
f
{ , , },
{ , , , },
{ }.
0
0
0
Γ
δ B is given by
δ
λ
B q
z
q z z
( , , )
{( ,
)}
′
′ =
′
0
0
1
0 0
δ
λ
B q
S
q aSb q aS q a
( , , ) {( ,
), ( , ), ( , )}
=
δ
λ
δ
B
B
q a a
q
q b b
( , , )
{( , )}
( , , )
=
=
δ
λ
λ
B
f
q
z
q
( , , )
{( , )}
1
0 ′ =
where
δ
δ
φ
B q a S
q a S
( , , )
( , , )
=
=
and
δ
δ
φ
B q b S
q b S
( , , )
( , , )
.
=
=
3.2 RELATIONSHIP BETWEEN PDA AND CONTEXT FREE
LANGUAGES
3.2.1 Sim plifying CFGs
The productions of context-free grammars can be coerced into a variety of
forms without affecting the expressive power of the grammar.
166
Theory of Automata, Formal Languages and Computation