108 CONTEXT-FREELANGUAGES
T + 1TO 1 lE#l 1 l#lOOD,
W + lW0 1 lE#Al 1 #AlOD,
S6 + UlD I VlD I AlPlD I AOQlD,
U + OUO 1 OUl 1 lU0 I 1Ulj OAOE# I lAOE#,
V + OVO I OVl I 1VO I 1Vl I OE#OA I OE#lA,
P + OPO 1 OPl I lP0 ( lP1 I OE#AO,
Q + OQO 1 OQl I lQ0 I lQ1 I OE#Al,
A + E I OA I lA, B+EIBBI#A, C+EICCIA#,
D + E I OD, E + E 1 1E. cl
Exercise 3.2
1. For each of the fol lowing lan
that generates the language:.guages, construct a context-free grammar(a) {aW 12i = 3j + 1).
(b) {aibj I2i # 3j + 1).
* (c) {“W I2i 5 3j < 4i). -
* (d) {aibj I2i + 3 < - 3j < - 4i - a).- For each of the following languages, construct a context-free grammar
that generates the language:
(a) {uitick I i 2 k or j > k}.
(b) {u%k+ I i+j = k}.-
(c) {uWck 1 j = i + k}.
(d) {uibjck I j > i + k - 3).
(e) {uWc” 1 i Tj # k + 3).
(f) {UWC” ) i + aj = k}.
(g) {uWck 1 i + 2j G k (mod 3)).
- (h) {uibkk I i + 2j = 3k).
- (i) {ui bjck 1 i + 2k 2 3j).
- (j) {uWC” 1 i + 2k 5 3j < 2i - + 3k).
- For each of the following languages, construct a context-free grammar
that generates the language:
(a) {uWc”d” I i + k = j + a).