Ì Exam ple 2.2.6: Obtain the language generated L(G) for a CFG given
G(N, T, P, S) with N = {S}, T{a}, P:
1
2
.
.
S
SS
S
a
→
→






Solu tion
S
SS
aS
aSS
aaS
aaa
⇒
⇒
⇒
⇒
⇒
and so on....
Therefore the language generated is
L G
a n
n
( ) { |
}
=
≥1
Ì Exam ple 2.2.7: Obtain the language generated by each of the following
production rules.
(a) A a
A aB
A
→
→
→ ∈
(b) S
aS
S
→
→ ∈
(c) A a
A aB
A
→
→
→ ∈
(d) A aS
S
bS
S
→
→
→ ∈
(e) S
aS
S
bS
S
a
→
→
→
(f) S
ab
S
bs
S a
S
b
→
→
→
→
Solu tion
(a) The language generated is a “type-3 language” or “regular set”.
(b) S
S
aS
a
S
as aaS
aa
⇒∈
⇒
⇒
⇒ ⇒
⇒
and so on.
Hence the language generated is
L G
a n
n
( ) { |
}
=
≥ 0
124
Theory of Automata, Formal Languages and Computation
S
S
S
a
a
S
SS
aS
aa
⇒
⇒
⇒
S
a
S
a
⇒