3.2 Examples of Context-Free Grammars 107
(a) If bi = 1” for some k > 0 then bi+l = 10’“.
(b) If bi = ~01’” for some u E l(0 + l)* and some k > - 0, then bi+l = ~10’“.
It follows from (a) and (b) that L2 = L3 U L4 U L5 U L6, whereL3 = {y#z 1 y, x E (0, l}*, y or x does not begin with l},
L4 = {l”#x 1 x E {o,l}*,k > 1,x # lo”),L5 = {U01”#v10~ (^1) % w E {o, 1), h # Q,
L6 = (uOl”#vlO~ 1 U, 21 E {0,1}, U # V}.
To simplify our job, we can further express LJ and L6 as unions of simpler
context-free languages:
L4 = {l”#Oh 1 k > 1, h > o} u {l”#lOh I k > 1, k # h}
u {l”#VlOh( k > - T, 21 E {o,1}+}; -
L6 = (uOl”#vlO~ I IUI # Iv]} u {u~lU~olk#w~Ow~lO~ I l?Jzl = Iwz1)
u (U~0U~01 k #wrlw210 h I 14 = Iwzl}
It is clear that each subset above is context-free. For instance, the language
(u11~201 k #WO~210 h I lual = Ivzl} can be generated by the following grammar
rules, starting with 5’6:
S6 + AlPlD, A + E I OA I lA,
D + E I OD, E -+ E 1 lE,
P + OPO 1 OPl 1 lP0 I 1Pl I OE#AO.
Combining the context-free grammars for all the above sets, we can find
a context-free grammar for L2. Further combining it with grammar G1, we
obtain a context-free grammar G for language L. This grammar G uses vari-
ables V = {S, 5’1,5’2,5’4, Sg, Sg, A, B, C, D, E, P, Q, U, V, W, T}, with S as the
starting symbol. The nonterminal symbols A, D, E, B, C represent simple
regular languages (0 + l)“, O, I, (#(0 + l)) and ((0 + l)#)*, respectively.
The nonterminal symbols S1, S2, 5’4, 5’s and S6 represent languages L1, L2,
Ld, L5 and L6, respectively. (Language 1;3 is a simple regular language that
can be generated directly from S2 .) The symbols P, Q, U, V, VV and T are
auxiliary symbols for languages Ld, L5 and LG. (Nonterminals U and V are
designed for the first subset of L 6, and P and Q for the other two subsets.)
The rules of G are as follows:
s + SlB 1 CS,B,
S1 I_) E 1 OA I 10A I OlA,
S2--+ #A)A#IOA#AIA#OAIs4Is5)Ss,
S4 + lE# I lE#OA I lE#lAlD IT,