Homework 3: Context-Free Grammars Homework solutions are required to be typeset, with the exception of state diagrams, which are allowed to be hand- drawn and included in a typeset document. Please see the Course Syllabus for the full homework formatting policy 1. Regular Grammars [5 points] Consider the following single-step grammar: A → OB 1C B → 0A 1D C→ 1A | ODE D→ 1B | 0C Give the state diagram for an NFA which decides the same language as this grammar. Your state diagram for this question may be handwritten. 2. Context Is Everything (Except for CFGs) [15 points] For each of the following languages, construct a context-free grammar that generates exactly the given language. (a) L₁ = {b¹aªa²x+³y : x, y ≥ 0}, Σ = {a,b} (b) LB (110|01)*000*, Σ = {0, 1} (c) Lc = binary strings with at most two 0's where the number of 1’s is equal to the number of 0's, Σ = {0, 1} 3. Noam, Is This Normal? [10 points] Convert the following grammar into Chomsky Normal Form, Σ = {0, 1}. Show your work at each of the five steps: START, BIN, DEL, UNIT, TERM (in that order). S→ OXY Y X → 1X | Y Y→S|0| E 1