1) Create a CFG which produces the strings a^nb^mc^m Example of accepted strings: abbcc, abc, aaabbbbcccc 2) Make the & operator in the following CFG left associative and the % operator right associative S -> a|b|S&S|S%S|e 3) Which string is not generated by the following context-free grammar? S -> SS* | SS+ | S- | N N -> 0 | 1 (a) 1--0+1+1* (b) 1-0*1+-0+- (c) 1-0+1-+*1- (d) 1-1-*0-+- 4) Which derivation is not a derivation in the following context-free grammar? S -> aS | bA | e A -> aA | bS | bB B -> aB | e (a) S => aS => abA => abbB => abbaB => abba (b) S => bA => baA => babS => babaS => babaaS => babaa (c) S => bA => baA => babS => babbA => babbbB => babbb (d) S => aS => abA => abbA => abbabB => abbab 5) Which statement is not true of the following context-free grammar? S -> SS | aSb | bSa | e (a) S =>* aabaabbb (b) S =>* bababbaa (c) S =>* baabbbaa (d) S =>* abbababb 6) Which statement is true of the following context-free grammar? S -> Ab | aaB A -> a | Aa B -> bS | b (a) bab has two leftmost derivations (b) aab has two leftmost derivations (c) aaab has two leftmost derivations (d) The grammar is unambiguous 7) The language generated by the following context-free grammar is inherently ambiguous, in the sense that every context-free grammar generating it is ambiguous. What language is this? S -> XC | AY X -> aXb | aA | bB Y -> bYc | bB | cC A -> aA | e B -> bB | e C -> cC | e (a) L1 = {a^i b^j c^i : i <> j} (b) L2 = {a^i b^j c^k : i <> k} (c) L3 = {a^i b^j c^k : i <> j v j <> k} (d) L4 = {a^i b^j c^k : i <> j & j <> k} 8) The following context-free grammar attempts to resolve the ambiguity in the grammar for conditional expressions by introducing nonterminals for conditionals with and without else branches. Which statement is true of this grammar? S -> S1 | S2 S1 -> if B S1 else S1 | skip S2 -> if B S | if B S1 else S2 B -> true | false (a) There is no derivation of 'if true skip else if true skip' in the grammar (b) The grammar is unambiguous (c) There are two rightmost derivations of 'if true if true skip else skip' (d) The else is associated with the outer if in 'if true if true skip else skip' 9) The following context-free grammar generates the language of regular expressions over the alphabet {a, b}. The union of two regular expressions u and v is written u + v rather than u | v. Which of the following statements is true of this grammar? A -> A + B | B B -> CB | C C -> C* | D D -> a | b | (A) (a) There are two leftmost derivations of a**b** (b) The Kleene star has lower precedence than concatenation (c) Concatenation is right-associative (d) Union has lower precedence than concatenation and the Kleene star