There fore
{
}
L G
a b n
n n
( )
;
=
≥ 0 .
Ì Exam ple 0.1.53: Obtain a Grammar which generates the language
{
}
L
a b
n
n n
=
≥
+1
0
:
Solu tion
With
{
}
L
a b n
n n
=
≥
: 0 , the grammar
(
)
G
S a b S P
= { }, { , }, ,
with production rules S
aSb S
→
→
,
.
λ
Therefore
{
}
L
a b
n
n n
=
≥
+1
0
:
is obtained by generating an extra b.
This is done with a production rule
S
Ab
→ .
Hence the grammar G is given by
(
)
G
S A a b S P
= { , }{ , }, , with pro duc tion rules given by
S
Ab
A aAb
A
→
→
→
,
λ
Ì Exam ple 0.1.54: Obtain the language L produced by G with production
rules
S
SS
S
S
aSb
S
bSa
→
→
→
→
,
λ
Solu tion
It is known from the given production rules that G has equal number of a’s and
b’s.
If w starts with an ‘a’ and ends with a ‘b’, then w L
∈ has the form
w a w b
=
1
where w L
1 ∈ .
If w starts with a ‘b’ and ends with an ‘a’ then w L
∈ has the form
w b w a
=
1
where w L
1 ∈ ..
Introduction
39