\documentstyle[11pt]{article}
% frob with the margins
\addtolength{\topmargin}{-1in}
\addtolength{\footskip}{-1in}
\addtolength{\textheight}{2in}
\addtolength{\oddsidemargin}{-.5in}
\addtolength{\evensidemargin}{-.5in}
\addtolength{\textwidth}{1in}
% no page numbers
\pagestyle{empty}
% counter for page numbers
\newcounter{pg}
\setcounter{pg}{2}

% DEFINE THE PROBLEM SET NUMBER
\def\psnum{6}

% DEFINE THE DUE DATE
\def\due{March 22, 1991}

% title command
\newcommand{\mytitle}{{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
% newpage setup command 
\newcommand{\mypage}[1]{\newpage{\large\noindent 6.045/18.400 Automata,
Computability, and Complexity \hfill{} Juliet Bourne \\
Problem Set \psnum \hfill{} \due \\}
\vspace{-.6in}
\begin{center} \rule{6in}{.25mm} \end{center}}
%\newcommand{\mynewpage}{\newpage\noindent
%{\large 6.045/18.400 \hfill{} Juliet Bourne \\
%Problem Set \psnum \hfill{} {\bf Page \thepg} \\}
%\vspace{-.6in}
%\begin{center}
%\rule{6in}{.25mm}
%\end{center}
%\addtocounter{pg}{1}}
% problem command
\newcommand{\prob}[1]{\noindent{\fbox{\large\bf Problem #1}}\vspace{.25in}}
% subproblem command
\newcommand{\subprob}[1]{\vspace{.15in} \noindent{\large\bf #1.}}
% equations commands
\newcommand{\beq}{\vspace*{-.3in}\begin{eqnarray*}}
\newcommand{\eeq}{\end{eqnarray*}}

\begin{document}

\mytitle

\prob{1: Unrestricted Grammars}

\noindent $L(G) = \{ ww : w \in \{a,b\}^*\}$ where $G = (V, \Sigma, R,
S)$. The basic idea is to create the string $ww^R$ and then reverse the
last half to get $ww$. The grammar looks like this:

\beq
V & = & \{a,b,S,P,Q,R,T,V,F\} \\
\Sigma & = & \{a,b\} \\
S & = & S 
\eeq

\noindent and the rules look like:

\beq
S & \rightarrow & PF | QF | \varepsilon \\
P & \rightarrow & aVa \\
Q & \rightarrow & bVb \\
V & \rightarrow & P | Q | T \\
aaF & \rightarrow & aRaF \\
abF & \rightarrow & bRaF \\
baF & \rightarrow & aRbF \\
bbF & \rightarrow & bRbF \\
aaR & \rightarrow & aRa \\
abR & \rightarrow & bRa \\
baR & \rightarrow & aRb \\
bbR & \rightarrow & bRb \\
TaR & \rightarrow & aT \\
TbR & \rightarrow & bT \\
TF & \rightarrow & \varepsilon 
\eeq

\mypage

\prob{2: Decidability and Acceptability}

\subprob{a} 

\noindent Steps:

\begin{enumerate}
\item Reject $\alpha$ if it is not a proper regular expression.
\item For each part for the regular expression (where parts are
separated by $\cup$'s): if $1^*$ appears, then accept and halt, since a
string of 111 is obviously a substring; if $0^*$ appears, remove it from
the regular expression, also removing any parantheses where appropriate;
if 111 appears, then accept and halt. Scan the part again, looking for
111; if it appears this time, accept and halt.
\item Reject.
\end{enumerate}

\subprob{b} Trying all possible strings $w \in L(G_1)$, if $w \not\in
L(G_2)$, which is a decidable question since $L_2$ is decidable, then
accept and halt.  Therefore, $L_b$ is Turing-acceptable since once it
encounters a string that is in one but not the other, it will accept.

\mypage

\prob{3}

\subprob{a}

\noindent Algorithm for the 2fa:

\begin{enumerate}
\item Move first head to the left. Read symbol. If the symbol is a 'c',
repeat 1. If symbol is a 'b', then move the second head left and go to
2. Otherwise, halt in a non-accepting state.
\item Move first head and second head to the left. If the first reads
'a' and the second reads 'b', go to 3. If the first reads 'b' and the
second reads 'c', then repeat 2. otherwise halt in non-accepting state.
\item Move first head and second head to the left. If the first reads
'a' and the second reads 'b', then repeat 3. If the first reads '\#' and
the second reads 'a', then enter the accepting halt state. Otherwise,
halt in a non-accepting state.
\end{enumerate}

\subprob{b} Knowing that deterministic finite automata will halt on any
given input, the $K_{2fa}$ can be shown to be recursive. The general
idea is like this:

\begin{enumerate}
\item Reject $x$ if it is not of the right format.
\item Give $x$ to $M$. If $M$ ends in the special halt state which
signifies acceptance, then accept and halt. Otherwise, reject and halt.
\end{enumerate}

\mypage

\prob{4: Symbol-Interleave of Two Languages}

\subprob{a} 

\noindent Let $M_1$ decide $L_1$ and $M_2$ decide $L_2$. Both $L_1$
and $L_2$ are Turing-decidable. General idea:

\begin{enumerate}
\item Give $x_1 ... x_m$ (by skipping over every other symbol) to $M_1$.
If $M_1$ rejects it, then reject. Otherwise it accepts, so go on to 2.
\item Similarly, give $y_1 ... y_m$ to $M_2$. If it rejects it, then
reject. Otherwise, it accepts, so accept and halt.
\end{enumerate}

\subprob{b}

\noindent Let $M_1$ accept $L_1$ and $M_2$ accept $L_2$. Both $L_1$ and
$L_2$ are Turing-acceptable. General idea:

\begin{enumerate}
\item Give $x_1 ... x_m$ to $M_1$. If it accepts, then go to 2.
\item Give $y_1 ... y_m$ to $M_2$. If it accepts, then accept and halt.
\end{enumerate}

\mypage

\prob{5: String-Interleave of Two Languages}

\subprob{a} (some help from Mike Bauer)

Yes, if $L_1$ and $L_2$ are Turing-decidable, then
$String-Interleave(L_1,L_2)$ is also Turing-decidable. The general idea
is to take dfa $M_1$ where $L(M_1) = L_1$ and dfa $M_2$ where $L(M_2) =
L_2$ and connect every state of $M_1$ to every state of $M_2$, and vice
versa, with empty transitions. This will mean that if at the end of the
input, both machines are halted in an accepting state, the input will be
accepted, since a division of the input was found such that it led to
an accepting path in both machines. Otherwise, the input will be
rejected. 

\subprob{b} Yes, same argument as above. If both machines accept, then
the input will be accepted.

\end{document}
