Solved-HomeWork #2- Solution

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.