Context-free Languages 1. Consider the following inductive definition of monomials and of polynomials in the variables a and b Monomials a and b are monomials every non-zero numeral is a monomial; e if n is a non-zero numeral and is either a or b, then r n is a monomial if m and m2 are two monomials, so is m1 m2; nothing else is a monomial Polynomials e0 is a polynomial; every monomial is a polynomial: if pi and p2 are two polynomials, so are pi + p2 and pi -p2 e nothing else is a polynomia (a) Write a context-free grammar for the language of monomials in the variables a and b over the alphabet {a, b, ^, ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (b) Write a context-free grammar for the language of polynomials in the variables a and b over the alphabet U {+,-) 2. Consider the grammar given by the production rules below, with start symbol B. over the alphabet which describes a subset of Java/F# Boolean expressions For each of the following words in ". first write a leftmost derivation of the word according to the grammar above.1 Then draw the corresponding parse tree. Recall that in a derivation only one non-terminal at a time gets rewritten. (a) x = y+a-1 Context-free Languages 1. Consider the following inductive definition of monomials and of polynomials in the variables a and b Monomials a and b are monomials every non-zero numeral is a monomial; e if n is a non-zero numeral and is either a or b, then r n is a monomial if m and m2 are two monomials, so is m1 m2; nothing else is a monomial Polynomials e0 is a polynomial; every monomial is a polynomial: if pi and p2 are two polynomials, so are pi + p2 and pi -p2 e nothing else is a polynomia (a) Write a context-free grammar for the language of monomials in the variables a and b over the alphabet {a, b, ^, ., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (b) Write a context-free grammar for the language of polynomials in the variables a and b over the alphabet U {+,-) 2. Consider the grammar given by the production rules below, with start symbol B. over the alphabet which describes a subset of Java/F# Boolean expressions For each of the following words in ". first write a leftmost derivation of the word according to the grammar above.1 Then draw the corresponding parse tree. Recall that in a derivation only one non-terminal at a time gets rewritten. (a) x = y+a-1