\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 A05}
\rhead{Due Fri, July 19, 11:59 PM EDT\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2024}

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

\providecommand{\SolutionNonCFLanguagesPartA}{}
\providecommand{\SolutionNonCFLanguagesPartB}{}
\providecommand{\SolutionClosureRulesForCFLsPartA}{}
\providecommand{\SolutionClosureRulesForCFLsPartB}{}
\providecommand{\SolutionClosureRulesForCFLsPartC}{}
\providecommand{\SolutionAlgorithmForPDAs}{}
\providecommand{\SolutionComputationsInATMPartA}{}
\providecommand{\SolutionComputationsInATMPartB}{}
\providecommand{\SolutionComputationsInATMPartC}{}
\providecommand{\SolutionComputationsInATMPartD}{}
\providecommand{\SolutionConstructATM}{}
\providecommand{\SolutionEveryCFLIsRecursive}{}

\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{ProblemNonCFLanguages}%
Non-context-free languages
\begin{enumerate}

\item \label{ProblemNonCFLanguagesPartA}%
Let \rmp{[4]}$\Sigma=\{ 0, 1 \}$.
Prove that the language
\begin{displaymath}
L_{a} = \left \{ 0^{i} 1^{j} \ | \ i = j^{2} \right \}
\end{displaymath}
is not context-free.
\SolutionNonCFLanguagesPartA

\newpage

\item \label{ProblemNonCFLanguagesPartB}%
Let \rmp{[4]}$\Sigma=\{ a \}$.
Prove that the language
\begin{displaymath}
L_{b} = \left \{ a^{n^{2}}\ | \ n \geq 0 \right \}
\end{displaymath}
is not context-free.
\SolutionNonCFLanguagesPartB
\end{enumerate}
}

\newpage

\item{ \label{ProblemClosureRulesForCFLs}%
Closure rules for CFLs\\
Recall that the \textbf{set difference} of two sets $S$ and $T$, denoted $S \setminus T$, is defined as
\begin{displaymath}
S \setminus T = \{ x \in S \ | \ x \notin T \}.
\end{displaymath}
\begin{enumerate}

\item \label{ProblemClosureRulesForCFLsPartA}%
Prove \rmp{[2]}that the class of context-free languages is \textbf{not} closed under set difference.
\SolutionClosureRulesForCFLsPartA

\newpage

\item \label{ProblemClosureRulesForCFLsPartB}%
Let \rmp{[2]} $L_{1}$ be a context-free language and let $L_{2}$ be a regular language.
Prove that $L_{1} \setminus L_{2}$ is a context-free language.
\SolutionClosureRulesForCFLsPartB

\newpage

\item \label{ProblemClosureRulesForCFLsPartC}%
Consider \rmp{[6]}two alphabets $\Sigma_{1}$ and $\Sigma_{2}$.
Let $Sub$ be any function $\Sigma_{1} \rightarrow \Sigma_{2}^{*}$ (i.e. $Sub$ replaces every $a \in \Sigma_{1}$ with some $w_{a} \in \Sigma_{2}^{*}$).
Then $LetSub$ is a \textbf{Letter Substitution} $L_{1} \rightarrow L_{2}$ if and only if
\begin{eqnarray*}
L_{2} & = & LetSub(L_{1}) \\
 & \underbrace{= }_{\textrm{Definition}} & \{ w \in \Sigma_{2}^{*} \ | \ \exists y \in L_{1} \textrm{, such that } w = y \textrm{, except that} \\
 & & \textrm{every character } c \textrm{ of } y \textrm{ has been replaced by } Sub(c) \} .
\end{eqnarray*}
Prove that the class of context-free languages is closed under Letter Substitution.
\SolutionClosureRulesForCFLsPartC
\end{enumerate}
}

\newpage

\item \label{QuestionAlgorithmForPDAs}
An algorithm for PDAs\\
Let \rmp{[6]}$P$ be an arbitrary PDA, with alphabet $\Sigma$.
Let $n > 0$ be an arbitrary positive integer.
Describe an algorithm to decide whether $P$ accepts any words $w \in \Sigma^{*}$ such that $|w| \leq n$.
\SolutionAlgorithmForPDAs

\newpage

\item{ \label{QuestionComputationsInATM}
Computations in a Turing machine\\
Let $M$ be a Turing Machine over the alphabet $\Sigma = \{ 0 \}$.
Let $M$'s tape alphabet be $\{ 0, X, B \}$.
Let $M$'s states be $\{ q_{1}, q_{2}, q_{3}, q_{4}, q_{5}, q_{6}, q_{7} \}$, with $q_{6}$ being the sole final state.
Let the transition function, $\delta $, for $M$, be defined by the following table.
\begin{center}
\begin{tabular}{ccc|ccc|ccc}
$q$ & $a$ & $\delta (q, a)$ & $q$ & $a$ & $\delta (q, a)$ & $q$ & $a$ & $\delta (q, a)$ \\
\hline 
$q_{1}$ & $0$ & $(q_{2}, B, R)$ & $q_{2}$ & $B$ & $(q_{6}, B, R)$ & $q_{4}$ & $X$ & $(q_{4}, X, R)$ \\
$q_{1}$ & $X$ & $(q_{7}, X, R)$ & $q_{3}$ & $X$ & $(q_{3}, X, R)$ & $q_{4}$ & $B$ & $(q_{7}, B, R)$ \\
$q_{1}$ & $B$ & $(q_{7}, B, R)$ & $q_{3}$ & $0$ & $(q_{4}, 0, R)$ & $q_{5}$ & $B$ & $(q_{2}, B, R)$ \\
$q_{2}$ & $X$ & $(q_{2}, X, R)$ & $q_{3}$ & $B$ & $(q_{5}, B, L)$ & $q_{5}$ & $0$ & $(q_{5}, 0, L)$ \\
$q_{2}$ & $0$ & $(q_{3}, X, R)$ & $q_{4}$ & $0$ & $(q_{3}, X, R)$ & $q_{5}$ & $X$ & $(q_{5}, X, L)$ \\
\end{tabular}
\end{center}
Let $M$ begin processing in the configuration $(q_{1}, \underline{w})$, where $w \in \Sigma ^{*}$ is the input word.

\begin{enumerate}
\item \label{QuestionComputationsInATMPartA}
Draw \rmp{[4]}a diagram for $M$.
\SolutionComputationsInATMPartA

\newpage

\item \label{QuestionComputationsInATMPartB}
Give \rmp{[4]}the sequence of instantaneous descriptions of $M$ as it processes the input word $w = 0000$.
\SolutionComputationsInATMPartB

\newpage

\item \label{QuestionComputationsInATMPartC}
Give \rmp{[4]}the sequence of instantaneous descriptions of $M$ as it processes the input word $w = 00000$.
\SolutionComputationsInATMPartC

\newpage

\item \label{QuestionComputationsInATMPartD}
Briefly \rmp{[2]}describe the algorithm which $M$ performs, given any input word $w \in \Sigma ^{*}$.
\SolutionComputationsInATMPartD
\end{enumerate}
}

\newpage

\item \label{QuestionConstructATM}
Constructing A Turing machine\\
Let \rmp{[10]}$\Sigma=\{ 0, 1 \}$.
Let $L_{1} = \{ 0^{i} 1^{j} \ | \ 0 \leq j \leq i \}$.
Let $L_{2} = \{ 0^{i} 1^{i} \ | \ 0 \leq i \}$.
Construct a Turing machine, $M$, which takes as input an arbitrary $w_{1} \in L_{1}$, and returns $w_{2} \in L_{2}$, such that $n_{0}(w_{1}) = n_{0}(w_{2})$.
Recall that $n_{0}(w)$ denotes the number of occurrences of the symbol $0$ in the string $w$.
In other words, $M$ appends $i-j$ copies of $1$ to the end of $w_{1}$, to produce the correct $w_{2}$.
For example, for input $w_{1} = 0001$, $M$ produces $w_{2} = 000111$.
Provide a diagram for your machine $M$.
\SolutionConstructATM

\newpage

\item \label{QuestionEveryCFLIsRecursive}
Every context-free language is recursive\\
Let $\Sigma $ \rmp{[6]}be a non-empty finite alphabet.
Let $G$ be an arbitrary context-free grammar over $\Sigma $, and let $L = L(G)$.
Give an algorithm for a Turing machine which decides membership in the language $L$.
%{\bf You do not need to give a detailed diagram for the Turing machine}, provided you describe your algorithm clearly enough.
Argue informally why your algorithm is correct.
\SolutionEveryCFLIsRecursive
\end{enumerate}

\end{document}