2012 Test 2

3.  Can list all palindromes by length, breaking ties by alphabetic order.

4.  Just run M for 1000 steps and see if it has not yet halted.

5.  This one is too close to assignment 8 for me to give you a hint on.

6a.  Use dovetailing.  For t=0,1,2,... try running M on each palindrome of length <= t for t steps.

6b.  No.

2012 Exam

1.  decidable, context-free, regular, context-free, recognizable, not recognizable, decidable, regular

2.  Keep track of whether you have seen 0, 1 or more than 1 a.  Do the same for b's.

3.  Hint:  the machine accepts strings that contain two a's in a row or two b's in a row.

4.  No.  Use pumping lemma

5.  L = {1^p : p is prime}

6.  nondeterministically choose to either
    push 0's and pop a 0 for each 1 or
    push 1's and pop a 1 for each 2.

7.  S -> S0 | S1 | T
    T -> 0T0 | 1T1 | U
    U -> U1 | U0 | #
    Figure out what each variable generates.

8.  3 and 4

9.  see text

10.  To answer this question, you should explain how to use material from this course to prove to your boss that the task he wants you to do is impossible in general.  (Then you might talk about heuristics that would help in some cases.)

11a.  Given x, run decide-L(x) and run decide-L'(x) and then combine the answers in the appropriate way.

11b.  L = all strings, L' = A_TM

12.  You could use a reduction from the complement of A_TM to L_12.

13a.  The property is not dependent only on the language of M, but on it's particular states.

13b.  Recognizable:  Use dovetailing.  Undecidable:  Use a reduction from the complement of E_TM.

14.  Hint:  use a breadth-first search of some graph.