Homework 5
MATH 421: Theory of Computation Due: March 15
Please submit a handwritten solution in class on the day above.
Show all work and justify all answers. This includes every step in your proofs.
25 points for each problem
1. Let B be the language of a generalized pushdown automaton with k stacks. Explain in detail how
to construct a Turing machine which recognizes B. (You may use a multitape Turing machine.)
2. Let M be a Turing machine (single-tape, deterministic – the basic model). Show how to construct a 2-stack pushdown automaton P with the same language as M. Hint: With two stacks, there is a natural way to identify a configuration of P with a configuration of a Turing machine.
3. Find a regular language that encodes the data structure in each of the following parts, if possible; if not possible, explain why not, and find a decidable language for this purpose, if possible; if still not possible, explain why not.
(a) A rational number
(b) A real number
(c) A finite rooted tree T = (V,E,r), where V is the vertex set, E ⊆ V is the edge set, and
r∈V istheroot
(d) A Turing machine
2
4. Design Turing machines to perform the following tasks. Here, if x ∈ N = {0, 1, 2, . . .}, then ⟨x⟩ denotes the natural encoding of x as a string over {0, 1} using the binary representation of x. In part (a), give the state diagram for a deterministic, single-tape Turing machine. In parts (b) through (d), you may present only a high-level description, and you may use nondeterministic or multi-tape Turing machines.
(a)Σ={0,1},t : Σ∗ →Σ∗,t(⟨w⟩)= ⟨w+1⟩. (b)Σ={0,1,#},t : Σ∗#Σ∗ →Σ∗,t(⟨w⟩#⟨x⟩)= ⟨w+x⟩ (c)Σ={0,1,#},t : Σ∗#Σ∗ →Σ∗,t(⟨w⟩#⟨x⟩)= ⟨w·x⟩
(d)Σ={0,1},t : Σ∗ →Σ∗,t(⟨x⟩)=1forallx∈P,t(⟨x⟩)=0forallx∈N−P,whereP is the set of all prime numbers.