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>cC.S>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}