HQ12

(a [2 points]) Let p denote the pumping length of a CFG G. Prove that G accepts infinitely many strings iff G derives some string w such that p <= |w| <= 2p-1.



(b [5 points]) Give an algorithm to determine if a CFG G accepts only finitely many strings. Briefly explain why your algorithm is correct. Analyse the complexity of your algorithm assuming that G has no rule of type "variable -> empty string", and that r denotes the number of rules, v denotes the number of variables, t denotes the number of terminals and the right-hand side of each rule has at most m symbols (from V U T).


(c [3 points]) Run your algorithm in (b) on this grammar: S -> a | T, T -> T.