1. Give context-free grammars that generate the following languages. (a) w E [O, 1) | w contains at least three 1s H Answer: G = (V, , R, S) with set of variables V = {S, X), where s is the start variable, set of terminals -(0,1): and rules S X1X1X1X (b) { w E {0, 1)' I w = u,R and 101 is even) Answer: G = (V, , R, S) with set of variables V = {S), where S is the start variable, set of terminals -(0, 1); and rules (c) { w E {0, 1)' l the length of u, is odd and the middle symbol is 0} Answer: G = (V, , R, S) with set of variables V = {S}, where s is the start variable set of terminals {0, 1); and rules S 0S0 | 0S1 | 1S0 | 1S1 | 0