need help with Q19 ?

Chapter 7 Pushdown Automata and Context-Free Languages a) Prove that the language Lj (abdi li, j 2 0 is context-free. b) Prove that the language L,-{a/bed i, j, k 0) is context-free. o) Prove that Lin L, is not context-free. Let L be the language consisting of all strings over fa, b) with 26. Pr 27. L 20. the same number of d and b's. Show that the pumping lemma is satisfied for L. That is, show thatevery z of length k or more has a decomposition that satisfies the conditions of the lemma. * 28. 21. Let M be a PDA. Prove that there is a decision procedure to determine whether a) L(M) is empty. b) L(M) is finite. c) L(M) is infinite. * 22. A grammar G = (V, ?, P S) is called linear if every rule has the form