CS 334: Problem Set 5

CS 334: Problem Set 5.
Problem 1. (10 points)
a) (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}.
b) (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.