Problem 1. (10 points)
(3 points) A 2-stack PDA is a PDA with two stacks; its input tape is 1-way read only. Describe, at a high-level, a 2-stack PDA to recognize the language { : , ≥ 0}.
(7 points) Can a 2-stack PDA recognize every Turing-recognizable language? Explain your reasoning.
Problem 2. (10 points) Let = {⟨ ⟩: ℎ }.
Show that is Turing-recognizable. Give a high-level description for your solution.
Problem 3. (10 points) Show that a language is decidable if and only if some enumerator enumerates the language in standard string order (lexicographically sorted in increasing length).
Problem 4. (10points) Show that every infinite TM-recognizable language has an infinite decidable subset.
