226 );! Theory of Computer Science
(c) {a lll b" Im :;t 11, m, n ~ I}, and
(d) {a
I Y"c" I m, 11 ~ I}.
6.17 Construct grammars in Greibach normal form generating the sets given
in Exercise 6.16.
6.18 If W E L(G) and Iw! = k, where G is in (i) Chomsky normal form,
(ii) Greibach normal form, what can you say about the number of steps
in the derivation of w7
6.19 Show that the language {d
,2 I11 ~ I} is not context-free.
6.20 Show that the following are not context-free languages:
(a) The set of all strings over {a, b, c} in which the number of
occurrences of a, b, c is the same.
(b) {a lll b lll c" 1m::; 11 ::; 2m}.
(c) {alllb" In = ml}.
6.21 A context-free grammar G is called a right-linear grammar if each
production is of the form A -7 wB or A -7 w, where A, B are variables
and w E L:*. (G is said to be left-linear if the productions are of the
form A -7 Bw or A -7 w. G is linear if the productions are of the form
A -7 vB-w or A -7 .v.) Prove the following:
(a) A right-linear or left-linear grammar is equivalent to a regular
grammar.
(b) A linear grammar is not necessarily equivalent to a regular
grammar.
6.22 A context-free grammar G is said to be self-embedding if there exists
some useful variable A such that A :b uAv, where u, v E L:*, u,
v :;t A, Show that a context-free language is regular iff it is generated
by a nonselfembedding grammar.
6.23 Show that every context-free language without A is generated by a
context-free grammar in which all productions are of the form A -7 a,
A -7 aab.