\documentclass[12pt]{article}
\usepackage{amsfonts, amssymb, amsmath, comment}
\usepackage[usenames,dvipsnames]{color}
\usepackage[pdftex]{graphicx}
\usepackage{fancyhdr}
\usepackage{hyperref}
\usepackage{url}
\usepackage{xypic}
\usepackage{tikz}
\usetikzlibrary{arrows,automata,shapes.geometric}
\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 A03}
\rhead{Due Wed, Feb 16, noon EST\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2022}

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

\providecommand{\SolutionProblemCFLPartA}{}
\providecommand{\SolutionProblemCFLPartB}{}
\providecommand{\SolutionProblemCFGPartA}{}
\providecommand{\SolutionProblemCFGPartB}{}
\providecommand{\SolutionProblemCFGAmbiguityPartA}{}
\providecommand{\SolutionProblemCFGAmbiguityPartB}{}
\providecommand{\SolutionProblemPushdownAutomatonPartA}{}
\providecommand{\SolutionProblemPushdownAutomatonPartB}{}

\input xy
\xyoption{all}

\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{ProblemCFL} Context-Free Languages\\
Let $\Sigma = \{ 0, 1 \}$.
\begin{enumerate}
\item
Let \rmp{[8]}$L_{a} = \{ w \ | \ w $ has odd length and its middle symbol is $ 0 \}$.
Give a context-free grammar $G_{a}$ such that $L(G_{a}) = L_{a}$, and prove that your choice of $G$ is correct.
\SolutionProblemCFLPartA

\newpage

\item
Consider \rmp{[8]}the context-free grammar $G_{b}$ with productions
\begin{eqnarray*}
S & \rightarrow & \varepsilon | 1S | 0T \\
T & \rightarrow & \varepsilon | 0T | 1U \\
U & \rightarrow & \varepsilon | 0T .
\end{eqnarray*}
Let $L_{b}$ be the language of words over $\Sigma $ which do {\bf not} have $011$ as a substring.
Prove that $L(G_{b}) = L_{b}$.
\SolutionProblemCFLPartB
\end{enumerate}

\newpage

\item \label{ProblemCFG}
A property of context-free grammars\\
Let $G$ be a context-free grammar and let $n > 0$ be a positive integer.
\begin{enumerate}
\item \label{ProblemCFGPartA}
Prove \rmp{[6]}that the number of words $w$ in $L(G)$ which are derived in $\leq n$ steps in $G$, is finite.
\SolutionProblemCFGPartA

\newpage

\item \label{ProblemCFGPartA}
Give \rmp{[2]}an example of a context-free grammar, $G$, in which we can generate infinitely many words $w$ provided we omit the hypothesis that there are $\leq n$ steps in the derivation of $w$.
Briefly explain why your example is correct.
\SolutionProblemCFGPartB
\end{enumerate}

\newpage

\item \label{ProblemCFGAmbiguity} Removing ambiguity in context-free grammars\\
Let $\Sigma = \{ 0, 1 \}$.
Consider the context-free grammar $G$ with productions
\begin{eqnarray*}
S & \rightarrow & AB \\
A & \rightarrow & \varepsilon | 0A \\
B & \rightarrow & \varepsilon | 01 | B1 .
\end{eqnarray*}
\begin{enumerate}
\item \label{ProblemCFGAmbiguityPartA} Prove \rmp{[4]}that $G$ is ambiguous.
\SolutionProblemCFGAmbiguityPartA

\newpage

\item \label{ProblemCFGAmbiguityPartB} Exhibit \rmp{[8]}(with proof) an unambiguous grammar, $G^{\prime }$, such that $L(G^{\prime }) = L(G)$.
\SolutionProblemCFGAmbiguityPartB
\end{enumerate}

\newpage

\item \label{Problem4} A pushdown automaton\\
Let $\Sigma = \{ 0, 1 \}$.
Consider this pushdown automaton, $P$:\\
  \begin{tikzpicture}[shorten >=1pt,%
      node distance=2.5cm,auto]
    \node[state,initial,accepting] at (0,2) (q_0) {$q_0$};
    \node[state](q_1) at (8,4) {$q_1$};
    \node[state](q_2) at (8,0) {$q_2$};
    \path[->]	(q_0) edge [bend left] node [above left] {$0,Z_{0}/0Z_{0}$} (q_1)
				(q_0) edge [bend right] node [below left] {$1,Z_{0}/1Z_{0}$} (q_2)
				(q_1) edge [bend left] node [right] {$1,Z_{0}/1Z_{0}$} (q_2)
				(q_2) edge [bend left] node [left] {$0,Z_{0}/0Z_{0}$} (q_1)
				(q_1) edge node [above left] {$\varepsilon,Z_{0}/Z_{0}$} (q_0)
				(q_2) edge node [below left] {$\varepsilon,Z_{0}/Z_{0}$} (q_0)
				(q_1) edge [loop right] node [right] {$\begin{array}{c} 0,0/00 \\ 1,0/\varepsilon \end{array}$} ()
				(q_2) edge [loop right] node [right] {$\begin{array}{c} 1,1/11 \\ 0,1/\varepsilon \end{array}$} ()
				;
  \end{tikzpicture}

\begin{enumerate}
\item
Give \rmp{[4]}an explicit sequence of instantaneous descriptions witnessing
\begin{displaymath}
(q_{0}, 0000, Z_{0}) \overset{*}{\vdash} (q_{1}, \varepsilon, 0000Z_{0}) .
\end{displaymath}
\SolutionProblemPushdownAutomatonPartA

\newpage

\item
Give \rmp{[4]}an explicit sequence of instantaneous descriptions witnessing
\begin{displaymath}
(q_{0}, 0110, Z_{0}) \overset{*}{\vdash} (q_{0}, \varepsilon, Z_{0}) .
\end{displaymath}
\SolutionProblemPushdownAutomatonPartB
\end{enumerate}

\end{enumerate}

\end{document}