15. Determine whether or not the language in Example 5.12 is linear.
16. Let G be a linear grammar with k variables. Show that when we write any
sequence of variables there must be some variable A that repeats so that
(a) the first occurrence of A must be in position p ≤ k,
(b) the repetition of A must be no later than q ≤ k +1, and
(c) there can be no other repeating variable between positions p and q.
17. Justify the claim made in Theorem 8.2 that for any linear language (not
containing λ) there exists a linear grammar without λ-productions and unitproductions.
18. Consider the set of all strings a/b, where a and b are positive decimal
integers such that a < b. The set of strings then represents all possible
decimal fractions. Determine whether or not this is a context-free language.
*19. Show that the complement of the language in Exercise 6 is not contextfree.
20. Is the language L = {a nm : n and m are prime numbers} context-free?
*21. It is known that the language
is not context-free. (See the next exercise.) Show that, in spite of this, it is
not possible to use Theorem 8.1 to prove it.
22. Ogden's lemma is an extension of Theorem 8.1 that necessitates some
changes in the way the pumping lemma game is played. In particular,
(a) You can choose any w ε L with |w| ≥ m, but you must mark at least m
symbols in w. You can choose which symbols to mark.
(b) The opponent must select the decomposition w = uvxyz with the
additional restriction that either vx or xy must have at least one marked
position.
Notice that Theorem 8.1 is a special case of Ogden's lemma in which all symbols
of ω are marked. Show how Ogden's lemma can be used to prove that the
language in the previous exercise is not context-free and conclude from this that
Ogden's lemma is more powerful than Theorem 8.1
16. Let G be a linear grammar with k variables. Show that when we write any
sequence of variables there must be some variable A that repeats so that
(a) the first occurrence of A must be in position p ≤ k,
(b) the repetition of A must be no later than q ≤ k +1, and
(c) there can be no other repeating variable between positions p and q.
17. Justify the claim made in Theorem 8.2 that for any linear language (not
containing λ) there exists a linear grammar without λ-productions and unitproductions.
18. Consider the set of all strings a/b, where a and b are positive decimal
integers such that a < b. The set of strings then represents all possible
decimal fractions. Determine whether or not this is a context-free language.
*19. Show that the complement of the language in Exercise 6 is not contextfree.
20. Is the language L = {a nm : n and m are prime numbers} context-free?
*21. It is known that the language
is not context-free. (See the next exercise.) Show that, in spite of this, it is
not possible to use Theorem 8.1 to prove it.
22. Ogden's lemma is an extension of Theorem 8.1 that necessitates some
changes in the way the pumping lemma game is played. In particular,
(a) You can choose any w ε L with |w| ≥ m, but you must mark at least m
symbols in w. You can choose which symbols to mark.
(b) The opponent must select the decomposition w = uvxyz with the
additional restriction that either vx or xy must have at least one marked
position.
Notice that Theorem 8.1 is a special case of Ogden's lemma in which all symbols
of ω are marked. Show how Ogden's lemma can be used to prove that the
language in the previous exercise is not context-free and conclude from this that
Ogden's lemma is more powerful than Theorem 8.1