As a string in L can begin and end with the same symbol, the string shoud
be of the form
w = w 1 w 2
where w 1 and w 2 are in L, produced by S → SS.
This generates the language
{
}
L
w n w n w
a
b
=
=
: ( )
( )
where n a (w) and n b (w) denotes the number of a’s and number of b’s in the
string w, respectively.
Ì Exam ple 0.1.55: Given
(
)
G
A S a b S P
1
1
= { , }, { , }, ,
with P 1 defined by
the production rules
S
aAb
A aAb
→
→
|
|
λ
λ
show that
{
}
L G
a b n
n n
( )
:
1
0
=
≥ .
Also show that G 1 is equivalent to G where
(
)
G
S a b S P
= { }, { , }, , where P
is given by
S
aSb
S
→
→ λ.
Solu tion
Given P 1 as
S
aAb
S
S
aAb
A
→
→
→
→
λ
λ.
S → λ pro duces a string with zero length. (n = 0)
S
aAb
a b
ab
S
aAb
aaAbb
aabb
a b
⇒
⇒
⇒
⇒
⇒
⇒
⇒
λ
2 2
and so on
Therefore L(G 1 ) = {a
n b
n : n ≥ 0}.
Given
(
)
G
S a b S P
= { }, { , }, , where P is S
aSb S
→
→
,
.
λ
The rule S
aSb
→
is recursive.
All sentential forms will have the forms
w a S b
i
i
i
=
40
Theory of Automata, Formal Languages and Computation