In this problem set, you can earn up to 100 + 10 (extra credit) points.
Problem 1. (5 + 5 + 10 = 20 points) Section 13.1, Exercise 4, page 894
Problem 2. (10 points) Section 13.1, Exercise 6 d), page 894
Problem 3. (10 points) Section 13.1, Exercise 14 b), page 894
Problem 4. (15 points 2 = 30 points) Consider the grammar G = (V; T; E; P ) for expressions (E for short) such that V = fE; a; +; ; (; )g; T = fa; +; ; (; )g; E is the starting symbol, and
◦ = fE ! (E) j E + E j E E j ag:
a) Explain whether G is regular, context-free, or context-sensitive, respectively. Explain why or why not.
b) Explain the language L(G) that is generated by G, especially, what kind of strings belong to the language. Be speci c. Also, give ve shortest strings that belong to L(G).
Problem 5. (5 points 2 = 10 points) Section 13.2, Exercise 4 a) and b), page 902. Explain by showing the state transition and the output of each state.
Problem 6. (10 points 2 = 20 points) Section 13.3, Exercise 8 e) and f), page 914. Prove or disprove.
f) False: jAnj 6= jAjn. Say that A = f1; 11g. Then A2 would be f11, 111, 1111g. This would mean that jAnj = 3, but jAjn = 4.
Problem 7. (5 points 2 = 10 points) Section 13.3, Exercise 10 b) and c) page 914. Explain.
3
