Problem Set 3 latex source
This file is provided to help students create their solutions
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\item[0.1] Read and solve, \underline{but do not turn in}: Book, 5.4
\ [$A \mapred B$ and $B$ is regular]
\item[0.2] Read and solve, \underline{but do not turn in}:
Show that $\lang{EQ}_\tm \not\mapred \atmbar$.
\item
Consider the problem of determining whether a given Turing machine $M$
on a given input $w$ ever attempts to move its head left when its head
is on the left-most tape cell. Formulate this problem as a language
and show that it is undecidable by using a reduction from $\atm$.
\item
Let $A$ be a language.
\begin{enumerate}
\item Show that $A$ is Turing-recognizable iff $A \mapred \atm$.
\item Show that $A$ is decidable iff $A \mapred \st0 \kstar \st1 \kstar$.
\end{enumerate}
\item
\begin{enumerate}
\item Let $\lang{FINITE}_\cfg=\setb{G}G$ is a \cfg\ and $L(G)$
is a finite language\setend. \\
Show that $\lang{FINITE}_\cfg$ is decidable.
\item Let $\lang{FINITE}_\tm=\setb{T}T$ is a \tm\ and $L(T)$
is a finite language\setend. \\
Show that $\lang{FINITE}_\tm$ is not T-recognizable.
\end{enumerate}
\item
Let $\lang{DISJOINT}_\cfg=\setb{G,H}G$ and $H$ are \cfgs\ and
$L(G)\inter L(H)=\emptyset$\setend. Show that \\ $\lang{DISJOINT}_\cfg$
is undecidable.
(Hint: Use a reduction from $\lang{PCP}$. Given an instance
\newcommand{\domino}[2]{\genfrac{[}{]}{}{}{\,#1\,}{\,#2\,}}
$$ P= \biggl\{
\domino{t_1}{b_1},\; \domino{t_2}{b_2},\; \ldots\;, \domino{t_k}{b_k}
\biggr\} $$
of the Post Correspondence Problem, construct \cfgs\ $G$ and $H$ with
the rules \begin{grammar}
G:\quad T \cfgarrow \, \makebox[.35in]{$t_1 T \st{a}_1$} \cfgor \cdots \cfgor
\makebox[.39in]{$t_k T \st{a}_k$} \cfgor
\makebox[.25in]{$t_1 \st{a}_1$} \cfgor \cdots \cfgor
\makebox[.28in]{$t_k \st{a}_k$} \\
H:\quad B \cfgarrow \, \makebox[.35in]{$b_1 B \st{a}_1$} \cfgor \cdots \cfgor
\makebox[.39in]{$b_k B \st{a}_k$} \cfgor
\makebox[.25in]{$b_1 \st{a}_1$} \cfgor \cdots \cfgor
\makebox[.28in]{$b_k \st{a}_k$}
\end{grammar}
where $\st{a}_1, \ldots, \st{a}_k$ are new terminal symbols.
Prove that this reduction works.)
\item
Define a \defin{two-headed finite automaton} (\twodfa) to be a deterministic
finite automaton that has two read-only, bidirectional heads that start at
the left-hand end of the input tape and can be independently controlled to
move in either direction. The tape of a \twodfa\ is finite and is just
large enough to contain the input plus two additional blank tape cells,
one on the left-hand end and one on the right-hand end, that serve as
delimiters. A \twodfa\ accepts its input by entering a special accept state.
For example, a \twodfa\ can recognize the language
$\set{ \st{a}^n \st{b}^n \st{c}^n} n \geq 0 \setend$.
\begin{enumerate}
\item Let $\atwodfa = \setb{M,x}M$ is a \twodfa\
and $M$ accepts $x \setend.$ Show that $\atwodfa$ is decidable.
\item Let $\etwodfa = \setb{M}M$ is a \twodfa\
and $L(M) = \nullset \setend$. Show that $\etwodfa$ is not decidable.
\end{enumerate}
\item
Give a Python program that prints itself out, in the spirit
of the recursion theorem. Submit a running program with its output.
You may use escape characters such as
\texttt{\textbackslash}\verb!"! and \texttt{\textbackslash\textbackslash}
but not special implementation features such as character codes or
pre-defined functions such as \texttt{repr()}. If you don't know Python,
you may use some other programming language. \\
(Hint: Assign a string to \texttt{S} to serve as a template.
The substring operation \texttt{S[i:j]} and escaped quotes are useful.)