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

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

\providecommand{\SolutionProblemCFLPartA}{}
\providecommand{\SolutionProblemCFLPartB}{}
\providecommand{\SolutionProblemCFLRegular}{}
\providecommand{\SolutionProblemCFGAmbiguityPartA}{}
\providecommand{\SolutionProblemCFGAmbiguityPartB}{}
\providecommand{\SolutionProblemCFGAmbiguityPartC}{}
\providecommand{\SolutionProblemPushdownAutomatonPartA}{}
\providecommand{\SolutionProblemPushdownAutomatonPartB}{}
\providecommand{\SolutionProblemPushdownAutomatonPartC}{}

\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\\
\begin{enumerate}
\item \label{ProblemCFL.1} Let \rmp{[10]}$T_{a} = \{ a, b \}$.
Give a context-free grammar, $G_{a}$, which generates the {\bf complement}, $(L_{a})^{\prime}$, of the language $L_{a} = \{a^{n} b^{n} \mid n \in 0,1,2, \ldots \}$ over $T_{a}$, and prove that your choice of $G_{a}$ is correct.
\SolutionProblemCFLPartA

\newpage

\item \label{ProblemCFL.2} Let \rmp{[10]}$T_{b} = \{ 0, 1, ! \}$.
Give a context-free grammar, $G_{b}$, which generates the language
\begin{displaymath}
L_{b} = \{w ! x \mid w, x \in \{ 0, 1 \}^{*} \textrm{ and } x \textrm{ contains } w^{R} \textrm{ as a substring} \},
\end{displaymath}
over $T_{b}$, and prove that your choice of $G_{b}$ is correct.
(For example, $0111 ! 11110 \in L_{b}$.)
\SolutionProblemCFLPartB

\end{enumerate}

\newpage

\item \label{ProblemCFLRegular}
Some context-free languages are regular\\
Let \rmp{[8]}$T = \{ 0, 1 \}$.
Suppose a language $L \subseteq T^*$ is accepted by some PDA, $P$, by final state (i.e. $L = L(P)$).
Suppose further that while processing any word $w \in T^*$, $P$'s stack never contains more than $3$ elements of the stack alphabet, $\Gamma$.
Prove that $L$ is \textbf{regular}.
\SolutionProblemCFLRegular

\newpage

\item \label{ProblemCFGAmbiguity} Removing ambiguity in context-free grammars\\
Define a context-free grammar $G = (V, T, P, S)$, where 
\begin{itemize}
\item $V = \{ S \}$
\item $T = \{ a, b \}$
\item $P = \{S \rightarrow aS | aSbS | \varepsilon \}$
\item $S = S$
\end{itemize}
\begin{enumerate}
\item \label{ProblemCFGAmbiguity.1} Prove \rmp{[2]} that $G$ is \textbf{ambiguous}, by exhibiting two different parse trees, two different leftmost derivations or two different rightmost derivations for the word $aab \in L(G)$.
\SolutionProblemCFGAmbiguityPartA

\newpage

\item \label{ProblemCFGAmbiguity.2} Prove \rmp{[8]}that
\begin{displaymath}
L(G) = \{ w \in T^{*} \mid \textrm{for every prefix } x \textrm{ of } w, \ n_{a}(x) \geq n_{b}(x) \} .
\end{displaymath}
\SolutionProblemCFGAmbiguityPartB

\newpage

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

\newpage

\item \label{ComputationInAPDA} A pushdown automaton\\
Define a pushdown automaton, $P = (Q, \Sigma, \Gamma, \delta, q, Z_{0}, F)$, accepting by final state, 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)
\item $F = \{ p \}$
\end{itemize}
and transition function
\begin{eqnarray*}
\delta (q, 0 , Z_{0}) & = & \{ (q, X Z_{0}) \} \\
\delta (q, 0 , X) & = & \{ (q, XX) \} \\
\delta (q, 1 , X) & = & \{ (q, X) \} \\
\delta (q, \varepsilon , X) & = & \{ (p, \varepsilon ) \} \\
\delta (p, \varepsilon , X) & = & \{ (p, \varepsilon ) \} \\
\delta (p, 1 , X) & = & \{ (p, XX ) \} \\
\delta (p, 1 , Z_{0}) & = & \{ (p, \varepsilon ) \} 
\end{eqnarray*}
\begin{enumerate}
\item \label{ComputationInAPDA.1} Draw \rmp{[2]}a diagram for $P$.
\SolutionProblemPushdownAutomatonPartA

\newpage

\item \label{ComputationInAPDA.2} Determine \rmp{[6]}all the instantaneous descriptions of the machine $P$ which can be reached after processing the input word $w = 01$.
\SolutionProblemPushdownAutomatonPartB

\newpage

\item \label{ComputationInAPDA.3} Using the definition of acceptance by final state, is \rmp{[2]}$01 \in L(P)$? Justify your answer.
\SolutionProblemPushdownAutomatonPartC
\end{enumerate}

\end{enumerate}

\end{document}