: 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 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.