Applying the production rule S
aSb
→
, we get
a S b
a S b
i
i
i
i
⇒
+
+
1
1
This is true for all i.
In order to get a sentence we apply S → λ.
Therefore we get
S
a S b
a b
n
n
n n
⇒
⇒
*
Hence
{
}
L G
a b n
n n
( )
:
=
≥ 0
Hence G 1 is equivalent to G as both the grammars are given by
{
}
a b n
n n : ≥ 0 .
Ì Exam ple 0.1.56: Given a grammar G defined by the production rules
S
AB
A
Aa
B
Bb
A a
B
b
→
→
→
→
→ .
Show that the word
w a b
L G
=
∈
2 4
( ),
where L is a language determined by G.
Solu tion
S
AB
AaB
aaB
aaBb
aaBbb
aaBbbb
aabbbb
a b
⇒
⇒
⇒
⇒
⇒
⇒
⇒
⇒
2 4
Hence the word w a b
L G
=
∈
2 4
( ).
Ì Exam ple 0.1.57: Find grammars for Σ = { , }
a b that generate the sets of
(a) all strings with exactly one ‘a’
(b) all strings with at least one ‘a’
(c) all strings with no more than three a’s.
Introduction
41