1. (25 points) Construct a pushdown automaton (PDA) for the complement of the following language: {ww:w{a,b}} 2. (25 points) Convert the following grammars to Chomsky normal form: S>aSa,S>B,B>bbC,B>bb,C>e,C>cCS>aTVa,T>aTabTbeV,V>cVce. 3. (25 points) Construct a Turing machine that converts binary numbers to their unary representations. e.g. on input 101 (the decimal equivalent of 5), the machine should output 111111 . You may use more than one tape. 4. (25 points) Construct a standard Turing machine to decide the following language: L={w{a,b,c,d},#b(w)#c(w)#d(w)0}