This is an open book, open note exam. Please turn in your work for this exam by 2:00.
1. Show that the language L = {x0y | x,y ∈ {0,1}* and |x| = |y|} is not regular.
2. Show that the language in problem 1 is context free.
3. Show that the language EQDFA = { <A,B> | A and B are DFAs that accept the same language } is decidable by testing both machines on all input strings up to some finite length. What length would work for this test?
4. Use the recursion theorem to prove that the language ETM = { <M> | M is a Turing machine that accepts no input } is undecidable.
5. In class I showed that the language
SUBSET-SUM = {<S,t> | S contains a subset whose sum is t }
is NP-Complete. Now consider the language
HALF = { <S> | S contains a subset whose sum is half the sum of all items in S }
Show that HALF is NP-Complete.