158 CONTEXT-FREE LANGUAGES(4 wR 1 x E L and xR E L} is context-free.
(e) {xxR ] x E L or xR $! L} is context-free.
0 1 xxR ] x E L and xR fif L} is context-free.* 11. Show that the set of all strings over alnhabet
that represent correct multiplication
2.65).- A context-free grammar G is called a linear grammar i
side of each rule of G contains at most one nonterminal
is not context-free (cf. Example
f the right-hand
symbols. A lan-
guage L is called a linear language if L = L(G) for some linear grammar
G. Show that for every linear language L, there exists a constant I< > 0
such that every string w in L with length lull > - K can be decomposed
as w = uvxyx satisfying the following conditions:(1) VY # &*
(2) luvyxl < Ii-. -
(3) Uvnxynz E L for all n > - 0.- Show that the following languages are not linear languages.
(a) {w E {o, 1)* I #o(w) = #l(W))*
* (b) {xy E {O,l}* ( Ix] = IyI,x # y}. [Hint: Apply the pumping
lemma for linear languages (Exercise 12 above) to a string w =
ambakbam with k > m. > I<. Note that a string aibajbat is not in
the language if j = i + Z]
* (4 { xxRwwR 1 x, w E {O,l)“}.