PLEASE ANSWER NUMBER 2 AND 3. IF YOUR KIND THEN ALSO ANSWER 4 AND 5. THANK YOU SO MUCH :))

2 Grammars and Parse Trees 1. For each of the following grammars, describe (in English) the language is described by the grammar. Describe the language, not the grammar. Example answer: "The language whose strings all contain one or more a's followed by zero or more b's followed optionally by c." Each grammar has only one non-terminal, S, serving as the start symbol. Terminal symbols are enclosed in quotes. a) S+081 01 b) S + + SS SS a c) S+S(S)SIC d) S + a SbSb SaSa e) S+ a SS SS S'*''(S' 2. Consider the following grammar, where (S) is the start symbol: (S) ::= (V) '=' (E) (S)';' (S) 'if' (B) 'then (S) 'if' (B) 'then' (S) 'elsel (S) (B) ::= (E) === (E) (V) ::= 'x' 'y' | 'z (E) ::= (V) '0'|'1' | 2 | 3* Consider the input if x === 1 then if y === 2 then z = 2 else z = 3." a) Demonstrate the ambiguity of the grammar by drawing as many parse trees as you can (at least 2 required) b) Write a new unambiguous grammar that generates the same language. c) Redraw the parse tree using the new grammar for the same string as above there should now 3. Consider the following grammar: (G) ::- (S) $$ (S) ::- (A) (M) (M) = (S) epsilon (A) ::= a (E) | b (A) (A) (E) := a (B) | b (1) | epsilon (B) ::= b (E) | a (B) (B) a) Describe in English the language that the grammar gencrates. b) Show a parse tree for the string a b a a. 4. Write a context-free grammar for each of the following languages: a) Strings of O's and 1's with an unequal number of O's and 1's (any order). b) Strings of O's and 1's that do not contain the substring 011. c) Strings of O's and 1's whose value is strictly greater than 5 when interpreted as a binary number. 5. Consider the following grammar: (A) = Add Aa (B) ::= Bc I b a) First, describe the language gencrated by this grammar. b) The above grammar cannot be parsed by an LL parser. Explain why. Refer to the lecture slides if you have difficulty. c) Rewrite the grammar so that can be pursed by an LL parser. You may use e transitions if you wish 2 Grammars and Parse Trees 1. For each of the following grammars, describe (in English) the language is described by the grammar. Describe the language, not the grammar. Example answer: "The language whose strings all contain one or more a's followed by zero or more b's followed optionally by c." Each grammar has only one non-terminal, S, serving as the start symbol. Terminal symbols are enclosed in quotes. a) S+081 01 b) S + + SS SS a c) S+S(S)SIC d) S + a SbSb SaSa e) S+ a SS SS S'*''(S' 2. Consider the following grammar, where (S) is the start symbol: (S) ::= (V) '=' (E) (S)';' (S) 'if' (B) 'then (S) 'if' (B) 'then' (S) 'elsel (S) (B) ::= (E) === (E) (V) ::= 'x' 'y' | 'z (E) ::= (V) '0'|'1' | 2 | 3* Consider the input if x === 1 then if y === 2 then z = 2 else z = 3." a) Demonstrate the ambiguity of the grammar by drawing as many parse trees as you can (at least 2 required) b) Write a new unambiguous grammar that generates the same language. c) Redraw the parse tree using the new grammar for the same string as above there should now 3. Consider the following grammar: (G) ::- (S) $$ (S) ::- (A) (M) (M) = (S) epsilon (A) ::= a (E) | b (A) (A) (E) := a (B) | b (1) | epsilon (B) ::= b (E) | a (B) (B) a) Describe in English the language that the grammar gencrates. b) Show a parse tree for the string a b a a. 4. Write a context-free grammar for each of the following languages: a) Strings of O's and 1's with an unequal number of O's and 1's (any order). b) Strings of O's and 1's that do not contain the substring 011. c) Strings of O's and 1's whose value is strictly greater than 5 when interpreted as a binary number. 5. Consider the following grammar: (A) = Add Aa (B) ::= Bc I b a) First, describe the language gencrated by this grammar. b) The above grammar cannot be parsed by an LL parser. Explain why. Refer to the lecture slides if you have difficulty. c) Rewrite the grammar so that can be pursed by an LL parser. You may use e transitions if you wish