\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CSG714}{Theory of Computation}{Spring 2008}{11 January 2007}{1}

\begin{center}
\Large{\bf Problem Set 1 (due Friday, January 25)}
\end{center}

{\bf 1. (7 points) [Sipser 1.48] A regular language}  

Let $\Sigma = \{0,1\}$ and let
\[
D = \{w | w \mbox{ contains an equal number of occurrences of the
substrings 01 and 10}\}.
\]
Thus, $101 \in D$ because 101 contains one 10 and one 01, but $1010
\notin D$ because 1010 contains two 10s and one 01.  Show that $D$ is
a regular language.

{\bf 2. (4 $\times$ 5 = 20 points) A non-regular language} 

Consider the language $F = \{a^i b^j c^k| i, j, k \ge 0 \mbox{ and if
} i = 1 \mbox{ then } j = k\}$.

\begin{itemize}
\item[{\bf (a)}] Show that $F$ is not regular,

\item[{\bf (b)}] Show that $F$ satisfies the conditions of the pumping
lemma.

\item[{\bf (c)}] Explain why parts (a) and (b) do not contradict the
pumping lemma.

\item[{\bf (d)}] Show that $F$ is context-free.
\end{itemize}

(Parts (a) through (c) are from [Sipser 1.54].)

{\bf 3. (8 points) Designing a Turing machine}

Design a Turing machine for the language of all strings with an equal
number of 0s and 1s.  The input alphabet is $\{0,1,\}$.

{\bf 4. (10 + 3 + 2 = 15 points) Input-read-only Turing machines} 

Define the {\em input-read-only}\/ Turing machine as a single tape
deterministic Turing machine that is not allowed to write on the
portion of the tape containing the input string.

\begin{itemize}
\item[{\bf (a)}]
Prove that input-read-only Turing machines can only recognize regular
languages.

\item[{\bf (b)}] Does the claim of part (a) hold if we allow the
input-read-only Turing machine to have {\em two heads}?  Briefly
justify your answer.  Note that we maintain the restrictions of a
single tape and that the portion of the input cannot be written into.

The definition of a two-head Turing machine is fairly natural.  The
transition function of a two-head Turing machine takes as input a
state and two symbols (one corresponding to each head) and returns a
state, two symbols to be written (one corresponding to each head), and
two moves (one corresponding to each head).  We can assume an
arbitrary tie-breaking mechanism for the scenario when two heads
attempt to write on the same cell.  Initially, both the heads are at
the leftmost end of the tape.

\item[{\bf (c)}] Does the claim of part (a) hold if we allow the
input-read-only Turing machine to have two tapes?  Briefly justify
your answer.
\end{itemize}

{\bf 5. (4 $\times$ 5 = 20 points) Classification of languages} 

Each of the following four parts gives a definition, description, or
some properties of a language.  In each case, tell whether the
language is:

A \hs  regular

B \hs  context-free but not regular

C\hs   Turing-decidable but not context-free

D\hs   not Turing-decidable

E\hs   there is insufficient information to tell.

Justify your answers with proofs, constructions, algorithms, or
examples as needed.

If, for example, you decide that a language is context-free but not
regular, you must give a context-free grammar that generates the
language or a pushdown automaton that accepts the language and also
prove that the language is not regular.

\begin{itemize}
\item[{\bf (a)}] $L = \{0^i1^j2^k \, | \, \mbox{ either } i+j = k
\mbox{ or } i + k = j \mbox{, and } i,j,k \ge 0\}$.  The input
alphabet is $\{0,1,2\}$.

\item[{\bf (b)}] $L = \{0^p  \, | p \mbox{ is prime}\}$.  The input
alphabet is $\{0\}$.

\item[{\bf (c)}] $L = \{ 01^m0 \, | \, m \mbox{ is a multiple of }
7\}$.  The input alphabet is $\{0, 1\}$.

\item[{\bf (d)}] $L$ is the set of balanced strings of three types of
  parentheses, (\, ) and [\, ] and \{, \}.  (For example,
  [\{[()()]\}(\{\})] is balanced, while \{([)]\} is not balanced.)
\end{itemize}
\end{document}
