1. Show that this language is decidable.
L1 = { <P,q> : P is a PDA, q is the only final state of P, and q is not visited by P during any transition on any input}.

2. Show that this language is decidable.
L2 = { <P,q> : P is a PDA and q is a useless state (not visited by P during any transition on any input) }

3. Show that the Halting problem is undecidable.

4. Say that string x is a prefix of string y if a string z exists where xz = y, and say that x is a proper prefix of y if in addition x != y. A language is prefix-free if it doesn’t contain a proper prefix of any of its members. Let L = {R : R is a regular expression such that L(R) is prefix-free }.
Show that L is decidable.

5. Consider the problem of determining whether a TM M on an input w ever attempts to move its head left at any point during its computation on w. Formulate this problem as a language and show that it is decidable.