1.(30 points) Using the following grammar, show a parse tree and a leftmost derivation for the following sentence (make sure you do not omit parentheses in your derivation. Parentheses, because they are terminal symbols, should have edges in your parse tree as well.):

Grammar = A | B | C + | * | () |

Derive

C = (A * (B + C) * C)

2. (20 points) Consider the following grammar (S is the start symbol; 0 and 1 are terminal symbols; A and B are non-terminals)

S 0A | 1B A 1B | 1 B 0A | 0

Explain, in your own words, what the grammar generates? Which of the following sentences are in the language generated by the grammar? Show derivations. If a sentence cannot be generated by the grammar, explain why.

1. 0001110
2. 1010101
3. 1100011
4. 0101010