CS 341 Homework 12Parse Trees 1. Consider the grammar G = ({+, *, (, ), id, T, F, E}, {+, *, (, ), id}, R, E}, where R = {E E+T, E T, T T * F, T F, F (E), F id}.Give two derivations of the string id * id + id, one of which is leftmost and one of which is not leftmost.2. Draw parse trees for each of the following: (a) The simple grammar of English we presented in class and the string "big Jim ate green cheese." (b) The grammar of Problem 1 and the strings id + (id + id) * id and (id * id + id * id).3. Present a context-free grammar that generates , the empty language.4. Consider the following grammar (the start symbol is S; the alphabets are implicit in the rules):S SS | AAA | A aA | Aa | b (a) Describe the language generated by this grammar. (b) Give a left-most derivation for the terminal string abbaba. (c) Show that the grammar is ambiguous by exhibiting two distinct derivation trees for some terminal string. (d) If this language is regular, give a regular (right linear) grammar generating it and construct the corresponding FSM. If the language is not regular, prove that it is not.5. Consider the following language : L = {wRw" : w {a, b}* and w" indicates w with each occurrence of a replaced by b, and vice versa}. Give a context-free grammar G that generates L and a parse tree that shows that aababb L.6. (a) Consider the CFG that you constructed in Homework 11, Problem 2 for {wcwR : w {a, b}*}. How many derivations are there, using that grammar, for the string aabacabaa? (b) Show parse tree(s) corresponding to your derivation(s). Is the grammar ambiguous?7. Consider the language L = {w {a, b}* : w contains equal numbers of a's and b's} (a) Write a context-free grammar G for L. (b) Show two derivations (if possible) for the string aabbab using G. Show at least one leftmost derivation. (c) Do all your derivations result in the same parse tree? If so, see if you can find other parse trees or convince yourself there are none. (d) If G is ambiguous (i.e., you found multiple parse trees), remove the ambiguity. (Hint: look out for two recursive occurrences of the same nonterminal in the right side of a rule, e.g, X XX) (e) See how many parse trees you get for aabbab using the grammar developed in (d).Solutions3. G = ({S} , , R, S), where R is any set of rules that can't produce any strings in *. So, for example, R = {S S} does the trick. So does R = .Homework 12 Parse Trees 14. (a) (a*ba*ba*ba*)* (b) S AAA aAAA abAA abAaA abbaA abbaAa abbaba (c) S S A A A A A A A a b b b a A b b b (d) G = ({S, S1, B1, B2, B3, a, b}, {a, b}, R, S), where R = {S S S1S1 aS1S1 bB1B1 aB1B1 bB2B2 aB2B2 bB3B3 aB3B3 B3 S1 a aS S1 b B1 bF B3 b B2 a a5. G = ({S, a, b}, {a, b}, R, S), R = { S aSb, S bSa, S } Sa S b a S b b S a 6. (a) The grammar is G = (V, , R, S) with V = {S, a, b, c}, = {a, b, c}, R = {S aSa, S bSb, S c}. There is a single derivation:S aSA aaSaa aabSbaa aabaSabaa aabacabaa (b) There is a single parse tree. The grammar is unambiguous.7. (a) G = (V, , R, S) with V = {S }, = {a, b }, R = {S aSbS bSaS S SS } (b) (i) S SS aSbS aaSbbS aabbaSb aabbab /* This is the leftmost derivation of the most "sensible" parse. (ii) S SS SSS aSbSS aaSbbSS aabbSS aabbaSbS aabbabS aabbab /* This is the leftmost derivation of a parse that introduced an unnecessary S in the first step, which was then eliminated by rewriting it as in the final step. (c) No. The two derivations shown here have different parse trees. They do, however, have the same bracketing,[a[ab]b][ab].(In other words, they have similar essential structures.) They differ only in how S is introduced and Homework 12 Parse Trees 2then eliminated. But there are other derivations that correspond to additional parse trees, and some of them correspond to a completely different bracketing, [a[ab][ba]b]. One derivation that does this is (ii) S aSb aSSb aabSb aabbab (d) This is tricky. Recall that we were able to eliminate ambiguity in the case of the balanced parentheses language just by getting rid of except at the very top to allow for the empty string. If we do the same thing here, we get R = { S S TT abT aTbT baT bTaT TTBut aabbab still has multiple parses in this grammar. This language is different from balanced parens since we can go back and forth between being ahead on a's and being ahead on b's (whereas, in the paren language, we must always either be even or be ahead on open paren). So the two parses correspond to the bracketings [aabb][ab] and [a [ab] [ba] b]. The trouble is the rule T TT, which can get applied at the very top of the tree (as in the case of the first bracketing shown here), or anywhere further down (as in the case of the second one). We clearly need somecapability for forming a string by concatenating a perfectly balanced string with another one, since, without that, we'll get no parse for the string abba. Just nesting won't work. We have to be able to combine nesting and concatenation, but we have to control it. It's tempting to think that maybe an unambiguous grammar doesn't exist, but it's pretty easy to see how to build a deterministic pda (with a bottom of stack symbol) to accept this language, so there must be an unambiguous grammar. What we need is the notion of an A region, in which we are currently ahead on a's, and a B region, in which we are currently ahead on b's. Then at the top level, we can allow an A region, followed by a B region, followed by an A region and so forth. Think of switching between regions as what will happen when the stack is empty and we're completely even on the number of a's and b's that we've seen so far. For example, [ab][ba] is one A region followed by one B region. Once we enter an A region, we stay in it, …
View Full Document