\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 - Winter 2022}
\chead{CM A05}
\rhead{Due Wed, March 23, noon EDT\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2022}

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

\providecommand{\SolutionProblemCFAndNonCFLanguagesPartA}{}
\providecommand{\SolutionProblemCFAndNonCFLanguagesPartB}{}
\providecommand{\SolutionProblemCFAndNonCFLanguagesPartC}{}
\providecommand{\SolutionProblemClosureRulesForCFLsPartA}{}
\providecommand{\SolutionProblemClosureRulesForCFLsPartB}{}
\providecommand{\SolutionProblemClosureRulesForCFLsPartC}{}
\providecommand{\SolutionQuestionComputationsInATMPartA}{}
\providecommand{\SolutionQuestionComputationsInATMPartB}{}
\providecommand{\SolutionQuestionComputationsInATMPartC}{}
\providecommand{\SolutionQuestionComputationsInATMPartD}{}
\providecommand{\SolutionQuestionRecursiveButNotCFL}{}
\providecommand{\SolutionQuestionEveryCFLIsRecursive}{}

\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{ProblemCFAndNonCFLanguages}%
Context-free and non-context-free languages
\begin{enumerate}

\item \label{ProblemCFAndNonCFLanguagesPartA}%
Prove \rmp{[4]}that the language
\begin{displaymath}
L_{a} = \left \{ w \in \{ 0, 1 \}^{*} \ | \ n_{1}(w) = n_{0}(w)^{2} \right \}
\end{displaymath}
is {\bf not} context-free.
Recall that $n_{1}(w)$ denotes the number of occurrences of the symbol $1$ in the string $w$, and $n_{0}(w)$ denotes the number of occurrences of the symbol $0$ in the string $w$.
\SolutionProblemCFAndNonCFLanguagesPartA

\newpage

\item \label{ProblemCFAndNonCFLanguagesPartB}%
Let \rmp{[4]}$\Sigma=\{ a, b, c \}$ be the alphabet for this part and for part \ref{ProblemCFAndNonCFLanguagesPartC}.
Prove that the language
\begin{displaymath}
L_{b} = \left \{ a^{i} b^{j} c^{k} \ | \ j \leq i \textrm{ or } k \leq i \right \}
\end{displaymath}
{\bf is} context-free.
\SolutionProblemCFAndNonCFLanguagesPartB

\newpage

\item \label{ProblemCFAndNonCFLanguagesPartC}%
Prove \rmp{[4]}that the complement, $L_{b}^{\prime}$, is {\bf not} context-free.
({\bf Remark:} This proves that $L_{b}$ is {\bf not} a DCFL.)
\SolutionProblemCFAndNonCFLanguagesPartC
\end{enumerate}
}

\newpage

\item{ \label{ProblemClosureRulesForCFLs}%
Closure rules for CFLs
\begin{enumerate}

\item \label{ProblemClosureRulesForCFLsPartA}%
Let \rmp{[2]} $L$ be a CFL and let $F$ be a finite language.
Prove that $L \setminus F = \{ w \in L \ | \ w \notin F \}$ is a CFL.
\SolutionProblemClosureRulesForCFLsPartA

\newpage

\item \label{ProblemClosureRulesForCFLsPartB}%
Let \rmp{[2]} $L$ be a {\bf non}-context-free language and let $F$ be a finite language.
Prove that $L \setminus F = \{ w \in L \ | \ w \notin F \}$ is a {\bf non}-context-free language.
\SolutionProblemClosureRulesForCFLsPartB

\newpage

\item \label{ProblemClosureRulesForCFLsPartC}%
Let \rmp{[2]} $L$ be a {\bf non}-context-free language and let $F$ be a finite language.
Prove that $L \cup F$ is a {\bf non}-context-free language.
\SolutionProblemClosureRulesForCFLsPartC
\end{enumerate}
}

\newpage

\item{ \label{QuestionComputationsInATM}
Computations in a Turing machine\\
Let $M$ be a Turing Machine over the alphabet $\Sigma = \{ 0, 1 \}$.
Let $M$'s tape alphabet be $\{ 0, 1, B \}$.
Let $M$'s states be $\{ q_{0}, q_{1}, q_{2}, q_{3}, q_{4}, q_{5}, q_{6}, q_{7}, q_{8} \}$, with $q_{8}$ 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$ & $x$ & $\delta (q, x)$ & $q$ & $x$ & $\delta (q, x)$ & $q$ & $x$ & $\delta (q, x)$ \\
\hline 
$q_{0}$ & $B$ & $(q_{1}, B, R)$ & $q_{2}$ & $B$ & $(q_{8}, B, R)$ & $q_{6}$ & $0$ & $(q_{6}, 0, R)$ \\
$q_{1}$ & $0$ & $(q_{1}, 0, R)$ & $q_{3}$ & $B$ & $(q_{4}, 0, R)$ & $q_{6}$ & $1$ & $(q_{6}, 1, R)$ \\
$q_{1}$ & $1$ & $(q_{1}, 1, R)$ & $q_{4}$ & $0$ & $(q_{4}, 0, R)$ & $q_{6}$ & $B$ & $(q_{7}, 1, L)$ \\
$q_{1}$ & $B$ & $(q_{2}, B, L)$ & $q_{4}$ & $1$ & $(q_{4}, 1, R)$ & $q_{7}$ & $0$ & $(q_{7}, 0, L)$ \\
$q_{2}$ & $0$ & $(q_{3}, B, R)$ & $q_{4}$ & $B$ & $(q_{7}, 0, L)$ & $q_{7}$ & $1$ & $(q_{7}, 1, L)$ \\
$q_{2}$ & $1$ & $(q_{5}, B, R)$ & $q_{5}$ & $B$ & $(q_{6}, 1, R)$ & $q_{7}$ & $B$ & $(q_{2}, B, L)$ \\
\end{tabular}
\end{center}
Let $M$ begin processing in the configuration $(q_{0}, \underline{B}w)$, where $w \in \Sigma ^{*}$ is the input word.

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

\newpage

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

\newpage

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

\newpage

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

\newpage

\item \label{QuestionRecursiveButNotCFL}
A language which is recursive but not context-free\\
Let \rmp{[8]}$\Sigma=\{ a, b, c \}$.
Recall from the lectures that this language is {\bf not} context-free:
\begin{displaymath}
L = \left \{ a^{i} b^{i} c^{i} \ | \ i \geq 0 \right \} .
\end{displaymath}
Give an {\bf algorithm} for a Turing machine that {\bf 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.
\SolutionQuestionRecursiveButNotCFL

\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$.
Argue informally why your algorithm is correct.
\SolutionQuestionEveryCFLIsRecursive
\end{enumerate}

\end{document}