\documentclass[12pt]{article}
\usepackage{amsfonts, amssymb, amsmath, comment}
\usepackage[usenames,dvipsnames]{color}
\usepackage[pdftex]{graphicx}
\usepackage{listings}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{url}
\usepackage{xypic}
\usepackage{epsf}
\usepackage{epsfig}
\usepackage{enumitem}

\setlist[itemize]{nosep}
\setlist[enumerate]{nosep}

\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.0in}
\setlength{\topmargin}{-0.5in}
\setlength{\headheight}{0in}
\parskip12pt
\parindent0pt
\pagestyle{fancy}
\lhead{CS 360 - Spring 2024}
\chead{CM A06}
\rhead{Due Tues, July 30, 11:59 PM\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2024}

\newcommand{\rmp}{\reversemarginpar\marginpar}

\providecommand{\SolutionDoubleStackPDA}{}
\providecommand{\SolutionReductionsPartA}{}
\providecommand{\SolutionReductionsPartB}{}
\providecommand{\SolutionDecidableLanguagesPartA}{}
\providecommand{\SolutionDecidableLanguagesPartB}{}
\providecommand{\SolutionAnUndecidableLanguagePartA}{}
\providecommand{\SolutionAnUndecidableLanguagePartB}{}

\input xy
\xyoption{all}

\newtheorem{DefinitionPlaceHolder}{Definition}
\newtheorem{TheoremContextFreeLanguagesAreRecursive}[DefinitionPlaceHolder]{Theorem}

\begin{document}

\begin{itemize}
\item{
Start as early as possible, and contact the instructor if you get stuck.
}
\item{
See the course outline for details about the course's marking policy and rules on collaboration.  
}
\item{
Submit your completed solutions to \textbf{Crowdmark}.
}
\end{itemize}

\begin{enumerate}

\item \label{QuestionDoubleStackPDA}
A double-stack PDA\\
Let \rmp{[8]}$M$ be an ordinary Turing machine (i.e. $M$ is a single-tape, deterministic TM).
Suppose that $M$ accepts (or does not accept) its input strings (i.e. $M$ does \textbf{not} compute a function).
Let $P$ be a PDA (accepting by final state), having two independent stacks, that both use the same stack alphabet, $\Gamma$.
$P$'s transition function, $\delta_{P}$, is therefore of the form
\begin{displaymath}
\delta_{P} : Q \times \left ( \Sigma  \cup\{ \varepsilon \} \right ) \times \Gamma \times \Gamma \rightarrow \textrm{ finite subsets of } Q \times \Gamma^{*} \times \Gamma^{*} .
\end{displaymath}
Describe how to construct such a $P$, so that $L(P) = L(M)$ (i.e. prove that every recursively enumerable language can be accepted by a double-stack PDA).
\begin{enumerate}[label=\roman*.]
\item{
Describe how to define the states (including the final states) of $P$.
}
\item{
Describe how to initialize both of $P$'s stacks, at the start of $P$'s execution.
}
\item{
Then describe how to define $\delta_{P}$ to simulate any single transition from $M$, inside of $P$.
}
\end{enumerate}

\SolutionDoubleStackPDA

\newpage

\item{ \label{QuestionReductions}
Reductions\\
Let $\Sigma = \{ 0, 1 \}$.
\begin{enumerate}
\item \label{QuestionReductionsPartA}
Let \rmp{[4]}$L$ be a language over $\Sigma $ such that $L \neq \emptyset $ and $L \neq \Sigma ^{*}$.
Let $L_{R}$ be \textbf{any} recursive language over $\Sigma $.
Prove that membership in $L_{R}$ can be reduced to membership in $L$.
\SolutionReductionsPartA

\newpage

\item \label{QuestionReductionsPartB}
Let \rmp{[4]}$L_{RE}$ be \textbf{any} recursively enumerable language over $\Sigma $.
Let $L_{u}$ be the {\bf universal language} as defined in the lecture slides.
(In detail, $L_{u}$ is the set of pairs $(e, w)$ such $e$ is the identifier of a Turing machine, $M$, which accepts the input word, $w$.)
Prove that membership in $L_{RE}$ can be reduced to membership in $L_{u}$.
\SolutionReductionsPartB
\end{enumerate}
}

\newpage

\item{ \label{QuestionDecidableLanguages}%
Decidable languages\\
Because of the \textbf{Church-Turing Thesis}, you only need to describe the required algorithm (e.g. in English or pseudocode) to decide the decision problem, in each part of this question.
You do \textbf{not} need to provide implementation details for a TM to decide each decision problem.
\begin{enumerate}
\item \label{QuestionDecidableLanguagesPartA}%
Consider \rmp{[4]}the language
\begin{displaymath}
L_{a} = \{ \langle D_{1}, D_{2} \rangle \ | \ D_{1}, D_{2} \textrm{ are DFAs and } L(D_{1}) \subseteq L(D_{2}) \} .
\end{displaymath}
Prove that (membership in) $L_{a}$ is decidable.

\SolutionDecidableLanguagesPartA

\newpage

\item \label{QuestionDecidableLanguagesPartB}%
Consider \rmp{[4]}the language
\begin{displaymath}
L_{b} = \{ \langle D, G \rangle \ | \ D \textrm{ is a DFA, } G \textrm{ is a CFG, and } L(G) \subseteq L(D) \} .
\end{displaymath}
Prove that (membership in) $L_{b}$ is decidable.

\SolutionDecidableLanguagesPartB
\end{enumerate}
}

\newpage

\item{ \label{QuestionAnUndecidableLanguage}
An undecidable language\\
Let $\Sigma $ be a finite alphabet containing the symbol $0$.
\begin{enumerate}

\item{ \label{QuestionAnUndecidableLanguagePartA}
Give \rmp{[3]}a reduction from membership in the language
\begin{displaymath}
L_{0+} = \{ w \ | \ w \textrm{ represents the Turing machine } M \textrm{ and } 0 \in L(M)\}
\end{displaymath}
to the membership in the language
\begin{displaymath}
L_{ \Sigma ^{*}} = \{ w \ | \ w \textrm{ represents the Turing machine } M \textrm{ and } L(M) = \Sigma ^{*} \} .
\end{displaymath}
\SolutionAnUndecidableLanguagePartA
}

\newpage

\item{ \label{QuestionAnUndecidableLanguagePartB}
Show that \rmp{[4]}the language $L_{0+}$ from part \ref{QuestionAnUndecidableLanguagePartA} is undecidable.
Do \underline{not} use Rice's theorem.
\SolutionAnUndecidableLanguagePartB
}
\end{enumerate}
}

\end{enumerate}

\end{document}