Exercise 9 (Multiple Choice). Consider the grammar G (note that stands for the empty string):

19. ::= aS | T
20. ::= bT | U
21. ::= cU |

1. Which of the following strings is generated by the grammar G?
   1. aba
   2. bab
   3. (c) ca

(d) ccc

2. Which of the following is a derivation of bbc in the grammar G?
   1. S T U bU bbU bbU bbc
   2. S bT bbT bbU bbcU bbc
   3. S T bT bbT bbU bbcU bbc
   4. S T bT bTbT bbT bbU bbcU bbc

Exercise 10 (Multiple Choice). Which of the following grammars describes the same language as 0^m1ⁿ where m n?

1. S ::= 0S1 |
2. S ::= 0S1 | S1 |
3. S ::= 0S1 | 0S |
4. S ::= SS | 0 | 1 |

Exercise 11. Consider the following grammar for abstract syntax of arithmetic expressions:

E ::= E+E | EE | EE | E/E | 1 | 2 | 3 | 4

with the usual associativity and precedence for the arithmetic operators (all operators are left-associative, and / have a higher precedence than + and ).

(1) Draw an abstract syntax tree for each of the following strings:

1. 1 2 + 3
2. 1 2 + 3
3. 1 2 3/4

(2) (Multiple Choice & Short Answer) Which of the following pairs of strings with different parentheses represent the same abstract syntax tree according to the above precedence and associativity? Draw that abstract syntax tree.

1. 2 4 3 versus 2 (4 3)
2. 1 + 2 + 3 + 4 versus 1 + (2 + (3 + 4))
3. 2 + 3 4/2 versus 2 + ((3 4)/2)