\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{Group Homework 4}
\duedate{Due: Saturday May 12, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
{\bf One member} of the group should upload your group submission to Gradescope.
During the submission process, they will be prompted to add the names of the rest
of the group members.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your homework must be typed. We recommend that you submit early drafts to Gradescope so that in
case of any technical difficulties, at least some of your work is present. You may update
your submission as many times as you'd like up to the deadline.\\
Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound.\\
{\sc Reading} Sipser Sections 2.1, 2.2, 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})
\begin{itemize}
\item[a.] Consider the PDA $M$ over the alphabet $\{ (, )\}$ with stack alphabet $\{ \$, X \}$ and state diagram
\begin{center}
\includegraphics[width=4in]{PDA2_HW4.png}
\end{center}
Build a CFG $G = (V, \Sigma, R, S)$ such that $L(G) = L(M)$.\\
{\it Hint:} $\varepsilon \in L(M)$, $(()) \in L(M)$, $(()()) \in L(M)$, but $( \notin L(M)$, $)( \notin L(M)$, $(() \notin L(M)$.\\
You do not need to justify your construction for credit, {\bf but} if you
describe how your grammar works by briefly describing the role of each variable and production rule,
we may be able to award partial credit if your answer is incorrect.
\end{itemize}
\end{problem}
\begin{problem}[1.](continued)
\begin{itemize}
\item[b.] Recall the first context-free grammar from this week's individual homework
\[
G_1 = ( \{ S, T \} , \{a,b,c\}, R_1, S)
\]
where $R_1$ is the set of rules containing
\begin{align*}
S &\to aSc ~\mid~ T \\
T &\to bTc ~\mid~ \varepsilon
\end{align*}
Build a PDA $M_1$ such that $L(M_1) = L(G_1)$.
Draw the state diagram of your PDA in JFLAP,
export the image as a png or jpg file, and include it as part
of your submission.
You do not need to justify your construction for credit, {\bf but} if you
describe how your state diagram works by briefly describing the role of each state and the transitions between them
we may be able to award partial credit if your answer is incorrect.
\item[c.] Recall the second context-free grammar from this week's individual homework
\[
G_2 = ( \{S, T, X \}, \{a,b,c\}, R_2, S)
\]
where $R_2$ is the set of rules containing
\begin{align*}
S &\to TbTSXbX ~\mid~ \varepsilon \\
T &\to aT ~\mid~ \varepsilon \\
X &\to cX ~\mid~ \varepsilon
\end{align*}
Build a PDA $M_2$ such that $L(M_2) = L(G_2)$.
Draw the state diagram of your PDA in JFLAP,
export the image as a png or jpg file, and include it as part
of your submission.
You do not need to justify your construction for credit, {\bf but} if you
describe how your state diagram works by briefly describing the role of each state and the transitions between them
we may be able to award partial credit if your answer is incorrect.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Let $L$ be the language over $\{0,1,2\}$ given by
\[
L = \{ 0^i 1^j 2^k \st i \geq 0, j \geq 0, k \geq 0, i \geq j+k \}.
\]
Build a CFG
$G = (V, \Sigma, R, S)$ generating the {\bf complement} of $L$, $\overline{L}$.\\
Include a brief justification of the role of each rule and production.\\
{\it Hints}: (1) Rewrite $\overline{L}$ as a union of simpler sets. (2) Refer back to this week's individual HW.
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) The alphabet for this problem is $\Sigma = \{a,b,c\}$. For this problem, briefly justify your answers to each of the following True/False questions.
\begin{itemize}
\item[a.] True / False: There is a non-context-free language over $\Sigma$ which has the string $abba$ as an element.
\item[b.] True / False: Every context-free language over $\Sigma$ is nonregular.
\item[c.] True/ False: There is a language that is generated by both an ambiguous CFG and an
unambiguous CFG.
\item[d.] True/ False: The union of two different context-free languages over $\Sigma$ is regular.\\
\end{itemize}
\end{problem}
\end{document}