\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth,multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Individual Homework 4}
\duedate{Due: Tuesday February 13, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW4} must be completed without any collaboration
with other students in this class. The only allowed sources of help for this homework
are the class textbook, notes, and podcast, and the instructional team. Two of the questions on this homework will be graded for fair effort completeness; one will be graded for correctness.
Your homework {\bf must be typed}. \\
{\sc Reading} Sipser Section 2.2, 2.1, examples from 2.3
\newline
{\sc Key Concepts} Pushdown automata, context-free
grammars, context-free languages, derivations, parse trees, ambiguous grammars,
leftmost derivations.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]({\bf 10 points})
Consider the language
\[
L = \{ a^{i} b^{i+j} a^{j} ~|~ i,j \geq 0 \}
\]
\begin{itemize}
\item[(a)] Here's an informal description of a PDA recognizing $L$.
\begin{quote}
Read symbols from the input. As each $a$ is read, push it onto the stack. As soon as $b$s are seen, pop an $a$
off the stack for each $b$ read. If the stack becomes empty, start pushing $b$s to it as we read them. As soon
as $a$s are seen, pop a $b$ off the stack for each $a$ read. If we reach the end of the string and the stack is
empty, accept. If the $a$s are finished while the stack still contains $b$s, or if any more $b$s appear in the input
following this second sequence of $a$s, reject the input.
\end{quote}
Draw its state diagram in JFLAP and include the image in your submission. {\it No justification necessary for this part.}
\item[(b)] A CFG generating $L$ is $G = (\{ S, T_1, T_2 \}, \{a,b\}, R, S)$ where the set
of rules is given by
\begin{align*}
S &\to T_1 T_2 \\
T_1 &\to a T_1 b ~|~ \varepsilon \\
T_2 &\to b T_2 a ~|~ \varepsilon
\end{align*}
Write out two {\bf derivations} for the string $aabbba$, one of which is
{\bf leftmost} and one of which is not. Is the grammar $G$ ambiguous?
{\it Justify your answers for this part.}
\end{itemize}
\end{problem}
\begin{problem}[2.] In IndivHW3, you showed that the class of regular languages over the alphabet $\{0,1\}$
is closed under the operation $Reverse(L)$.
\begin{itemize}
\item[(a)] To prove that the class of context-free languages over the same alphabet is closed under the same operation,
would it be enough to use the facts that (1) the class of regular languages is a subset of the class of
context-free languages and (2) the class of regular languages is closed under Reverse? Why or why not?
\item[(b)] To prove that the class of context-free languages over the same alphabet is closed under Reverse
directly, consider the context-free grammar $G = (V, \{0,1\}, R, S)$. Define a (new) CFG $G' = (V', \{0,1\}, R', S')$
where
\begin{align*}
V' &= \underline{\phantom{Fill in the blank here}} \qquad \text{This will
be the set of variables for your new grammar} \\
R'&= \underline{\phantom{Fill in the blank here}} \qquad \text{This will be the set of rules in your new grammar}
\\
S' &= \underline{\phantom{Fill in the blank here}}
\qquad \text{This is your new start variable. Make sure you choose an element
of $V'$.}
\end{align*}
(by filling in the blanks above) such that $L(G') = Reverse( ~L(G) ~)$.
{\it You do not need to give a formal proof that your construction works, but explain
in a sentence or two why you defined the construction in this way.}
\item[(c)] Since CFGs and PDAs are equivalently expressive, we could have approached this problem using PDAs.
Would you expect it to be harder or easier to prove the closure of the class of context-free languages under
Reversal using PDAs?
\end{itemize}
\end{problem}
\begin{problem}[3.] For the alphabet $\Sigma = \{ a,b \}$ find languages $A, B, C$ over
$\Sigma$ where
$A \subsetneq B \subsetneq C$ and
\begin{itemize}
\item $A$ is nonregular and context-free,
\item $B$ is regular, and
\item $C$ is nonregular and context-free.
\end{itemize}
Briefly justify
the subset inclusions and either prove or cite examples in the book to explain why you chose each set.
\end{problem}
\end{document}