Description
Problem 1 (0.5 points)
Prove that all regular languages are CFLs.
Problem 2 (2 points)
Prove that the language L = {x | x is not of the form ww, w ∈ {0, 1}∗}
is a CFL.
Problem 3 (1.25 points)
Consider the following extension to Turing Machines. The transition function is
of the form δ(q, σ, D) = (q’, σ’, D’) where D is the direction the head moved
the last time it visited this cell. (If it never visited this cell before, then
D defaults to LEFT.) Does this provide additional power to the Turing Machine?
Why or why not?
Problem 4 (1.25 points)
Consider a Turing Machine with a 2-dimensional tape. The head now has 4 possible
moves, up, down, left, or right. (Everything else is analogous to a standard
Turing Machine.) Prove that a Turing Machine with a 2-dimensional tape can be
simulated by a standard Turing Machine.