\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 A04}
\rhead{Due Wed, March 9, noon EST\\
\small 5\% penalty per hour late in submitting}
\cfoot{\normalfont\medskip Copyright \copyright 2022}

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

\providecommand{\SolutionProblemPushdownAutomaton}{}
\providecommand{\SolutionProblemCFGFromPDAPartA}{}
\providecommand{\SolutionProblemCFGFromPDAPartB}{}
\providecommand{\SolutionProblemAnalogOfKleenesTheorem}{}
\providecommand{\SolutionProblemDPDAsAndDCFLs}{}
\providecommand{\SolutionProblemCNFPartA}{}
\providecommand{\SolutionProblemCNFPartB}{}

\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{Problem4} A pushdown automaton\\
Let \rmp{[6]}$\Sigma = \{ 0, 1 \}$.
Construct a pushdown automaton, $P$, which accepts exactly the language
\begin{displaymath}
L = \{ w \in \Sigma ^{*} \ | \  \textrm{every prefix of } w \textrm{ has at least as many } 0 \textrm{s as } 1 \textrm{s} \} .
\end{displaymath}
State explicitly whether $P$ accepts by final state or by empty stack.
Argue informally why your $P$ accepts exactly $L$.
\SolutionProblemPushdownAutomaton

\newpage

\item \label{Problem5} Building a context-free grammar from a PDA\\
Define the pushdown automaton, $P = (Q, T, \Gamma, \delta, q, X)$ (which accepts by empty stack), with
\begin{itemize}
\item $Q = \{ q \}$
\item $T = \{ 0, 1 \}$
\item $\Gamma = \{ 0, 1, X \}$
\item $q$ = start state for machine
\item $X$ = stack start letter
\end{itemize}
and transition function
\begin{enumerate}
\item[1.]{$\delta (q, \varepsilon , X) = \{ (q, \varepsilon ), (q, 0X1) \}$}
\item[2.]{$\delta (q, 0, 0) = \{ (q, \varepsilon ) \}$}
\item[3.]{$\delta (q, 1, 1) = \{ (q, \varepsilon ) \}$}
\end{enumerate}
\begin{enumerate}
\item \label{Problem5a} Draw \rmp{[2]}a diagram for $P$.
\SolutionProblemCFGFromPDAPartA

\newpage

\item \label{Problem5b} Use \rmp{[4]}the technique described on slides 51-54 of Module 6 to construct a context-free grammar, $G$, such that $L(G) = N(P)$.
In your final grammar, replace the non-terminals from the construction with single capital letters $A, B, C, \ldots$.
Simplify your grammar as much as possible after you have completed the construction.
You do \textbf{not} have to prove that $L(G) = N(P)$.
But you should convince yourself that the equality holds once you have completed the construction and simplification of $G$.
\SolutionProblemCFGFromPDAPartB
\end{enumerate}

\newpage

\item \label{ProblemAnalogOfKleenesTheorem}
The analog of Kleene's Theorem for CFLs and PDAs\\
Let \rmp{[8]}$\Sigma $ be an alphabet.
For any language $L$ over $\Sigma $, Define
\begin{displaymath}
SUFFIX(L) = \{ y \ | \ xy \in L \textrm{, for some string } x \in \Sigma ^{*} \} .
\end{displaymath}
Prove that the class of context-free languages over $\Sigma $ is closed under the $SUFFIX$ operation.
\SolutionProblemAnalogOfKleenesTheorem

\newpage

\item \label{ProblemDPDAsAndDCFLs}
Deterministic PDAs and DCFLs\\
Prove \rmp{[6]}that the language
\begin{displaymath}
L = \left \{ x!y \ | \ x \neq y^{R} \textrm{ and } x, y \in \{ 0, 1 \}^{*} \right \}
\end{displaymath}
is a DCFL, by giving a natural DPDA for it and explaining how that DPDA works.
Your machine should accept by final state.
\SolutionProblemDPDAsAndDCFLs

\newpage

\item \label{ProblemCNF}
Recall from Slide 18 of Module 5, a grammar for words having a balanced number of $0$s and $1$s:
\begin{displaymath}
G : S \rightarrow \varepsilon \mid  0S1 \mid  1S0 \mid  SS .
\end{displaymath}
\begin{enumerate}
\item
Use \rmp{[8]}the technique on slides 6-17 of Module 7 to produce a grammar, $G^{\prime}$, in Chomsky Normal Form, such that $L(G) = L(G^{\prime}) \cup \{ \varepsilon \}$.
You do \textbf{not} need to prove this equality of languages: following the algorithm correctly will guarantee this fact.
\SolutionProblemCNFPartA

\newpage

\item
Give \rmp{[4]}an explicit derivation, in $G^{\prime}$, for the word: $0101$.
\end{enumerate}
\SolutionProblemCNFPartB

\end{enumerate}

\end{document}