PROBLEM SET 3, CSC 280, 2006 DUE BEFORE CLASS, WED. FEB. 15 The third problem set is as follows. All 10 problems will be marked out of the same total. Answers to any 7 (reduced from 8) questions make a complete answer paper. However, you can do all questions to earn bonus points. TO FACILITATE THE GRADING PROCESS, PLEASE PUT YOUR ANSWERS TO SEPARATE QUESTIONS ON SEPARATE PAGES, AND PLACE YOUR ANSWERS IN THE SAME ORDER AS THE QUESTIONS, I.E., ANSWERS TO Q1, ANSWERS TO Q2, ETC. THANK YOU! Keep your eyes on the instructor's and the TAs' web site for any corrections or discussion. PROBLEM 1 ~~~~~~~~~ Call a CFG 'recursive' if for some variable A there is a derivation A => x where A occurs in x; call a variable A of a CFG with start symbol S 'unreachable' if A is not S and there is no derivation S => x where A occurs in x; and call a variable A of a CFG 'unproductive' if there is no derivation A => x where x is a terminal string. (A variable that is either unreachable or unproductive is sometimes called "useless".) a. Show that any CFG generates an infinite language only if it is recursive, i.e., only if for some variable A there is a derivation A => x where A occurs in x. (Hint: the most intuitive way to think about this might be in terms of root-to-leaf paths in parse trees.) b. Construct a CFG which is recursive, has no unreachable or unproductive variables, and no productions A -> B (where A, B are variables), yet generates a finite language containing at least two strings. c. Convert your CFG from (b) to CNF, using the procedure covered in class (and in the text). Problem 2 ~~~~~~~~~ Show that allowing regular expressions on the RHS of CFG rules still yields only context-free languages. An example of such a generalized rule would be A -> (B U C)*a+, where this can be thought of as standing for infinitely many rules A -> a, A -> aa, ..., A -> Ba, A -> Baa, ..., A -> Ca, A -> Caa, ..., A -> BBa, A -> BCa, A -> CBa, A -> CCa, A -> BBaa, A -> BCaa, etc. Problem 3 ~~~~~~~~~ The following grammar rules are used in the Sipser text, p. 108 (Example 2.10) to illustrate the conversion to CNF: S -> ASA | aB, A -> B | S, B -> b | e (where e is the empty string) a. Propose a simple characterization of the language generated by these rules (where the start symbol is S); it should look like this: L = {w | w fulfills some condition}. Hint: Experiment with generating very short strings, to get a feel for what can be generated. b. Prove that your characterization is correct, using an inductive argument. Hint: The basis of the induction should be concerned with the shortest possible string(s), and the induction might then consider the possibility of such derivations as S => aS and S => Sb. PROBLEM 4 ~~~~~~~~~ The proof used in the text that PDAs recognize all CFLs could be viewed as based on top-down nondeterministic parsing (or as based on leftmost derivations); similarly the proof used in class also takes this perspective (though using CNF). a. Provide an alternative construction based on bottom-up nondeterministic parsing. Here is the general idea (steps 2-4 amount to a "reduction", in parsing terminology): 0. Push $ onto the stack; Repeat 1-4: 1. Shift 0 or more input symbols onto the stack; 2. Select a rule R: A -> x nondeterministically; 3. Match the symbols of x, in reverse order, against the stack symbols (with no action required if x is epsilon); {thus |x| stack symbols are consumed; match failure leads to a deadend state -- which can be left implicit}; 4. {All of x is matched} If A is the start symbol and the stack symbol is $, restore the $, enter an accept state and push A onto the stack; otherwise push A onto the stack without entering an accept state. b. Provide a proof that your PDA in part (a) recognizes the language generated by the given CFG. Suggestions: Show that your PDA (in effect) successfully cycles through steps 1-4, choosing a rule R and placing a variable A on the stack (without otherwise altering the stack), iff it has consumed a string from the input that is derivable from A via rule R (as first step), since the time at which the previous top-of-stack symbol (on which A is placed) was added to the stack. For this proof, use induction on the heights of parse trees for the derivation of a terminal string from A via rule R. PROBLEM 5 ~~~~~~~~~ Consider the PDA M = ({q,q',q"},{a,b}, {A}, delta, q, {q',q"}), where (with e denoting the empty string) delta(q,a,e) = {(q,A)}, delta(q,e,e) ={(q',e)}, delta(q,b,A) ={(q",e)}, delta(q',e,A) = {(q',e)}, delta(q",b,A) = {(q",e)}, delta(q",e,A) ={(q",e)}. a. Give the state diagram of M. b. Concisely describe the language L(M) acepted by M . PROBLEM 6 ~~~~~~~~~ Construct PDAs that accept each of the following languages (where a^i denotes "a repeated i times", & similarly for b^j, etc.): a. {a^ib^j | i =/= j} b. {w | w is in {a,b}* and has a prefix containing more a's than b's} PROBLEM 7 ~~~~~~~~~ Construct PDAs that accept each of the following languages: a. {a^ib^jc^k | i+k = j} b. {w | W is in {a,b}* and has twice as many a's as b's} PROBLEM 8 ~~~~~~~~~ Construct a PDA with only two stack symbols (say, Gamma = {0,1}) for {wdw^R | w is in {a,b,c}*} (where w^R is the reverse of w). PROBLEM 9 ~~~~~~~~~ Construct a PDA for the grammar (with S as start symbol) S -> aABA | aBB, A -> bA | b, B -> cB | c, using the technique employed in proving that PDAs recognize the CFLs (in class and in the book; the technique in the lecture slides depends on use of Chomsky normal form). Remark: this grammar is in so-called Greibach Normal Form; note that every production generates 1 terminal, which is initial (but S -> e is allowed, as in CNF). PROBLEM 10 ~~~~~~~~~~ Consider the PDA M = ({q,q',q"},{a,b},{A},delta,q,{q"}), where delta(q,a,e) = {(q,A)}, delta(q,b,A) ={(q',e)}, delta(q',b,e) = {(q",e)}, delta(q",b,A) = {(q',e)}. a. Give the state diagram of M. b. Give a concise description of L(M). c. Calculate the number of grammar rules that result if the construction in the proof that all PDAs recognize CFLs is applied. Do not write out the rules -- this would be very tedious!