Question
Exercise 8 (Multiple Choice) . Let X be inductively defined as the smallest set of finite number lists (taken from N ) satisfying the following
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 [x1,x2,x3,...,xn] already in X, the set X also contains the list [x1,x2,x3,...,xn,y] where the additional element y is the product x1 x2 x3 xn.
Which of the following lists is NOT in X?
- [1,1,1,1,1]
- [2,4,16,256]
- (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):
- ::= aS | T
- ::= bT | U
- ::= cU |
- Which of the following strings is generated by the grammar G?
- aba
- bab
- (c) ca
(d) ccc
- Which of the following is a derivation of bbc in the grammar G?
- S T U bU bbU bbU bbc
- S bT bbT bbU bbcU bbc
- S T bT bbT bbU bbcU bbc
- S T bT bTbT bbT bbU bbcU bbc
Exercise 10 (Multiple Choice). Which of the following grammars describes the same language as 0m1n where m n?
- S ::= 0S1 |
- S ::= 0S1 | S1 |
- S ::= 0S1 | 0S |
- 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 2 + 3
- 1 2 + 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.
- 2 4 3 versus 2 (4 3)
- 1 + 2 + 3 + 4 versus 1 + (2 + (3 + 4))
- 2 + 3 4/2 versus 2 + ((3 4)/2)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started