(e) L = {a n b j c k : n
(h) L = {w ε {a,b,c}* : n a (w)+ n b (w) = 2n c (w),n a (w)= n b (w)}.
(i) L = {a n b m : n and m are both prime}.
(j) L = {a n b m : n is prime or m is prime}.
(k) L = {a n b m : n is prime and m is not prime}.
8. Determine whether or not the following languages are context-free.
(a) L={a n ww R a n : n ≥ 0, w ε {a,b}*}
(b) L= {a n b j a n b j : n ≥ 0, j ≥ 0}.
(c)L= {a n b j a j b n : n ≥ 0, j ≥ 0}.
(d)L= {a n b j a k b l : n + j ≤ k + l}.
(e)L= {a n b j a k b l : n ≤ k, j ≤ l}.
(f)L= {a n b n c j : n ≤j}.
(g)L= {w ε {a, b, c}* : n a (w)= n b (w)=2n c (w)}.
9. In Theorem 8.1, find a bound for m in terms of the properties of the grammar
G.
10. Determine whether or not the following language is context-free.
11. Show that the language L = {a n b n a m b m : n ≥ 0,m ≥ 0} is context-free but not
linear.
12. Show that the following language is not linear.
13. Show that the language
is contextfree, but not linear.
14. Determine whether or not the language
is linear.
(h) L = {w ε {a,b,c}* : n a (w)+ n b (w) = 2n c (w),n a (w)= n b (w)}.
(i) L = {a n b m : n and m are both prime}.
(j) L = {a n b m : n is prime or m is prime}.
(k) L = {a n b m : n is prime and m is not prime}.
8. Determine whether or not the following languages are context-free.
(a) L={a n ww R a n : n ≥ 0, w ε {a,b}*}
(b) L= {a n b j a n b j : n ≥ 0, j ≥ 0}.
(c)L= {a n b j a j b n : n ≥ 0, j ≥ 0}.
(d)L= {a n b j a k b l : n + j ≤ k + l}.
(e)L= {a n b j a k b l : n ≤ k, j ≤ l}.
(f)L= {a n b n c j : n ≤j}.
(g)L= {w ε {a, b, c}* : n a (w)= n b (w)=2n c (w)}.
9. In Theorem 8.1, find a bound for m in terms of the properties of the grammar
G.
10. Determine whether or not the following language is context-free.
11. Show that the language L = {a n b n a m b m : n ≥ 0,m ≥ 0} is context-free but not
linear.
12. Show that the following language is not linear.
13. Show that the language
is contextfree, but not linear.
14. Determine whether or not the language
is linear.