1. What language is described by the following grammar? SAB, A-, B-ab 2. Construct phrase-structure grammars that generate each of the following languages a. {012 | n0} b. {0^12nn 20} c. {1"101"O" | m 20 and n 2 0} 3. Let G = (V, T, S,P) be a grammar, with V = {a, b, A, S), T= {a, b), and P consisting of the following productions: Sbs, saaA, AA, and Aa. a. Show that bbaaba belongs to the language generated by G by showing a derivation tree. b. Show that abab does not belong to the language generated by G. c. What is the language generated by G? 4. The following grammar is in Backus Naur form. ::= () | + * | :=xly ber a. Express this grammar in phrase-structure form. b. Find a derivation tree for (x*(y + )) + y in this grammar. 5. Draw a finite state machine that recognizes the language {0'10 | n 2 1}. States ICH