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

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

\providecommand{\SolutionProblemPushdownAutomaton}{}
\providecommand{\SolutionProblemCFGFromPDAPartA}{}
\providecommand{\SolutionProblemCFGFromPDAPartB}{}
\providecommand{\SolutionProblemCFGFromPDAPartC}{}
\providecommand{\SolutionProblemCFGFromPDAPartD}{}
\providecommand{\SolutionProblemAnalogOfKleenesTheoremPartA}{}
\providecommand{\SolutionProblemAnalogOfKleenesTheoremPartB}{}
\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{ProblemPushdownAutomaton} A pushdown automaton\\
Give \rmp{[6]}a PDA that accepts the language of even-length words that are \underline{not} palindromes over the alphabet $\Sigma = \{ a, b \}$.
Your machine may accept by final state or by empty stack, whichever is more convenient.
State explicitly whether your machine accepts by final state or by empty stack.
Explain why your PDA is correct.
\SolutionProblemPushdownAutomaton

\newpage

\item \label{ProblemCFGFromPDA} Building a context-free grammar from a PDA\\
Define a pushdown automaton, $P = (Q, \Sigma, \Gamma, \delta, q, Z_{0})$ (which accepts by empty stack), with
\begin{itemize}
\item $Q = \{ q, p \}$
\item $\Sigma = \{ 0, 1 \}$
\item $\Gamma = \{ Z_{0}, X \}$
\item $q$ = start state for machine
\item $Z_{0}$ = stack start letter (bottom of stack character)
\end{itemize}
and transition function
\begin{enumerate}
\item[1.]{$\delta (q, 0, Z_{0}) = \{ (q, X Z_{0}) \}$}
\item[2.]{$\delta (q, 0, X) = \{ (q, XX) \}$}
\item[3.]{$\delta (q, 1, Z_{0}) = \{ (p, Z_{0}) \}$}
\item[4.]{$\delta (q, 1, X) = \{ (p, X) \}$}
\item[5.]{$\delta (p, 0, X) = \{ (p, \varepsilon ) \}$}
\item[6.]{$\delta (p, \varepsilon , Z_{0}) = \{ (p, \varepsilon ) \}$}
\end{enumerate}
\begin{enumerate}
\item \label{ProblemCFGFromPDAPartA} Draw \rmp{[2]}a diagram for $P$.
\SolutionProblemCFGFromPDAPartA

\newpage

\item \label{ProblemCFGFromPDAPartB} Use \rmp{[8]}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

\newpage

\item \label{ProblemCFGFromPDAPartC} The \rmp{[4]}construction in part \ref{ProblemCFGFromPDAPartB} can introduce some productions which will never resolve all of their variables.
Simplify the grammar you found in part \ref{ProblemCFGFromPDAPartB} by eliminating all such productions.
If this leaves some variables without any productions, then eliminate those variables as well.
\SolutionProblemCFGFromPDAPartC

\newpage

\item \label{ProblemCFGFromPDAPartD} Give \rmp{[5]}a ``nice" description of $L(G)$, and prove that your description is correct.
(You do not need to include this parenthesized part in your solution, but you should also confirm that your description of $L(G)$ makes sense with respect to the definition of the original PDA, $P$.)
\SolutionProblemCFGFromPDAPartD
\end{enumerate}

\newpage

\item \label{ProblemAnalogOfKleenesTheorem} \label{ProblemAnalogOfKleenesTheorem}%
The analog of Kleene's Theorem for CFLs and PDAs\\
Let $\Sigma$ be an alphabet.
\begin{enumerate}
\item \label{ProblemAnalogOfKleenesTheorem.1}%
Let \rmp{[6]}$D$ be an arbitrary DFA, with alphabet $\Sigma$.
Describe a construction for an $\varepsilon$-NFA, $E$, which, given any input word $w \in \Sigma^{*}$,
\begin{enumerate}[i]
\item{accepts no non-empty words, and}
\item{accepts the empty word, $\varepsilon$, if any only if $D$ accepts $w$.}
\end{enumerate}
Briefly explain why your construction of $E$ is correct.
\SolutionProblemAnalogOfKleenesTheoremPartA

\newpage

\item \label{ProblemAnalogOfKleenesTheorem.2}%
Let \rmp{[8]}$L_{1}, L_{2}$ be languages over $\Sigma$.
Define
\begin{displaymath}
L_{1} / L_{2} = \{ w \ | \ wx \in L_{1} \textrm{, for some } x \in L_{2} \} .
\end{displaymath}
Suppose that $L_{1}$ is context-free, and $L_{2}$ is regular.
Prove that $L_{1} / L_{2}$ is context-free.
(Hint: use part \ref{ProblemAnalogOfKleenesTheorem.1}.)
\SolutionProblemAnalogOfKleenesTheoremPartB
\end{enumerate}

\newpage

\item \label{ProblemDPDAsAndDCFLs}
Deterministic PDAs\\
Suppose \rmp{[4]}that $D$ is a DPDA whose set of final states is $F$, and that accepts $L(D)$ by final state.
Let $D^{\prime }$ be the same DPDA, but with final states $Q \setminus F$ (that is, the accept states of $D^{\prime }$ are those states that are not accept states of $D$.
Is it always the case that $L(D^\prime)$ equals the complement of $L(D)$?
Prove your answer.
\SolutionProblemDPDAsAndDCFLs

\newpage

\item \label{ProblemCNF}
Recall from Slides 13--17 of Module 5, a grammar for the language $\{ 0^{i} 1^{j} \ | \ 0 \leq i \leq j \}$ is:
\begin{displaymath}
G : S \rightarrow \varepsilon \mid 0S1 \mid  S1 .
\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: $00111$.
\end{enumerate}
\SolutionProblemCNFPartB

\end{enumerate}

\end{document}