Chapter 4: Formal Languages ~ 113
EXAMPLE 4.5
If Gis S ~ as i ItS [ a [ h, find L(G).
Solution
We sho\v that U C) = {a. b} 7 . As V·le have only two terminals a, h,
UG) :;;;;; {a. b} *. All productions are S-productions. and so A can be in L(G)
on1\ when S ~ A is a production in the grammar G. Thus.
UG) :;;;;; {a. h} ':' - {A} = {a, b} +
To show {Cl, b r : ; ; ; ; ; ICG). consider any string al a: ... ali' where each ai
is either a or h. The first production in the delivation of ClI{l2 ... all is S ~
as or 5 ~ bS according as a] = a or (lj = b. The subsequent productions are
obtained in a similar way. The last production is S ~ a or S ~ b according
as
= a or a" = b. So aja2 ... ali E UG). Thus. we have L(G) = {a, h ]+.
EX~RCISE If G is S ~ as [a, then show that L(G) = {a} +
Some of the following examples illustrate the method of constructing a
grammar G generating a gi ven subset of stlings over E. The difficult P
de\clop productions generating the strings in the given subset of E*.
EXAMPLE 4.6
Let L be the set of all pahndromes over {a. h}. Construct a grammar G
generating L.
Solution
S=>b
S => (I,
For constructing a grammar G generating the set of all palindromes. \ve use
the recursive definition (given in Section 2.4) to observe the following:
ii) A is a palindrome.
Iii) a. b are palindromes.
(Jii) If x is a palindrome axo. then bxb are palindromes.
So \\e define P as the set consisting of:
S ~.\
S ~ (f and S ~ b
Oii) S ~ aSa and S ~ hSb
Let G = ({5} {a. b}, P. S). Then
5 => A,
The. fore.
A. a. h E L(G)
If x is a palindrome of even length, then x =a1a2 .. " ([III {[ill . • • a!, where
"'3" ron ' 's el"tJ'e~ '1 (), lJ Tlf1e11 S =>':' " -
(,1"1 a
'I b\' app'''l'TIa
....... ~ L Ui L
_d
1
L.
~
•
i .
d \ U2 . .. .'1! (Ii; !1i-l ... l-1
"..: <:: _ If b
S --" aSa or S ~ bSb. Thus. x E L(G).
EXAMPLE 4.5
If Gis S ~ as i ItS [ a [ h, find L(G).
Solution
We sho\v that U C) = {a. b} 7 . As V·le have only two terminals a, h,
UG) :;;;;; {a. b} *. All productions are S-productions. and so A can be in L(G)
on1\ when S ~ A is a production in the grammar G. Thus.
UG) :;;;;; {a. h} ':' - {A} = {a, b} +
To show {Cl, b r : ; ; ; ; ; ICG). consider any string al a: ... ali' where each ai
is either a or h. The first production in the delivation of ClI{l2 ... all is S ~
as or 5 ~ bS according as a] = a or (lj = b. The subsequent productions are
obtained in a similar way. The last production is S ~ a or S ~ b according
as
= a or a" = b. So aja2 ... ali E UG). Thus. we have L(G) = {a, h ]+.
EX~RCISE If G is S ~ as [a, then show that L(G) = {a} +
Some of the following examples illustrate the method of constructing a
grammar G generating a gi ven subset of stlings over E. The difficult P
de\clop productions generating the strings in the given subset of E*.
EXAMPLE 4.6
Let L be the set of all pahndromes over {a. h}. Construct a grammar G
generating L.
Solution
S=>b
S => (I,
For constructing a grammar G generating the set of all palindromes. \ve use
the recursive definition (given in Section 2.4) to observe the following:
ii) A is a palindrome.
Iii) a. b are palindromes.
(Jii) If x is a palindrome axo. then bxb are palindromes.
So \\e define P as the set consisting of:
S ~.\
S ~ (f and S ~ b
Oii) S ~ aSa and S ~ hSb
Let G = ({5} {a. b}, P. S). Then
5 => A,
The. fore.
A. a. h E L(G)
If x is a palindrome of even length, then x =a1a2 .. " ([III {[ill . • • a!, where
"'3" ron ' 's el"tJ'e~ '1 (), lJ Tlf1e11 S =>':' " -
(,1"1 a
'I b\' app'''l'TIa
....... ~ L Ui L
_d
1
L.
~
•
i .
d \ U2 . .. .'1! (Ii; !1i-l ... l-1
"..: <:: _ If b
S --" aSa or S ~ bSb. Thus. x E L(G).