Exercise 8 (Multiple Choice). Let X be inductively defined as the smallest set of finite number lists (taken from N) satisfying the following closure properties:

• Given any natural number n from N, the set X contains the one-element list [n].
• Given any list [x₁,x₂,x₃,...,x_n] already in X, the set X also contains the list [x₁,x₂,x₃,...,x_n,y] where the additional element y is the product x₁ x₂ x₃ x_n.

Which of the following lists is NOT in X?

1. [1,1,1,1,1]
2. [2,4,16,256]
3. (c) [3,3,9,81]

(d) [4,4,16,256]

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)