\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~}
\newcommand{\derives}{\implies}
\name{}
\class{CSE 105}
\assignment{Individual Homework 4}
\duedate{Due: Tuesday May 8, 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.\\
Your homework {\bf 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.\\
{\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}) Consider the context-free grammars
\[
G_1 = ( \{ S, T \} , \{a,b,c\}, R_1, S) \qquad \qquad G_2 = ( \{S, T, X \}, \{a,b,c\}, R_2, S)
\]
where $R_1$ is the set of rules containing
\begin{align*}
S &\to aSc ~\mid~ T \\
T &\to bTc ~\mid~ \varepsilon
\end{align*}
and $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*}
To show that a string is in $L(G_i)$, we give a derivation of the string using the rules in $R_i$. For example, the
derivation
\[
S \derives aSc \derives aTc \derives abTcc \derives abcc
\]
proves that $abcc \in L(G_1)$.
\begin{itemize}
\item[a.] Is the empty string in $L(G_1)$? Is the empty string in $L(G_2)$?
\item[b.] Show that the string $abbccc$ is in $L(G_1)$ by giving a derivation of it using the rules in $R_1$.
\item[c.] Show that the string $abbccc$ is in $L(G_2)$ by giving a derivation of it using the rules in $R_2$.
\item[d.] Is $L(G_1)$ infinite? Is $L(G_2)$ infinite?
\item[e.] Is $L(G_1) \subseteq L( a^* b^* c^*)$? Is $L(G_2) \subseteq L( a^* b^* c^*)$?
\end{itemize}
{\it No justifications required for credit for this question; but, as always, they're a good idea for your own benefit.}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}). In class (Monday April 29), we proved that every regular set is PDA-recognizable
by modifying the state diagram of an NFA to get a PDA. In the book on page 107, the top paragraph describes a procedure
for converting DFA to CFGs:
\begin{quote}
You can convert any DFA $M = (\{ q_0, \ldots, q_n \}, \Sigma, \delta, q_0, F)$
into an equivalent CFG as follows. Make a variable $R_i$ for each state $q_i$ of the DFA.
Add the rule $R_i \to a R_j$ to the CFG if $\delta( (q_i, a) ) = q_j$ is a transition in the DFA. Add the rule
$R_i \to \varepsilon$ if $q_i$ is an accept state of the DFA. Make $R_0$ the start variable of the grammar.
\end{quote}
Consider the state diagram of a DFA recognizing the language $A = L(0^* 1^* 2^*)$.
\begin{center}
\includegraphics[width=4in]{DFA_HW4.png}
\end{center}
\begin{itemize}
\item[a.] What would the {\bf input alphabet} of a PDA recognizing the {\bf complement} of $A$ be?
What would the {\bf stack alphabet} of a PDA recognizing the {\bf complement} of $A$ be?
Draw the state diagram of this PDA recognizing the {\bf complement} of $A$.
\item[b.] Use the process above to build a CFG $G$ generating the {\bf complement} of $A$. Specifically, fill in the blanks
below: $G = (V, \Sigma, R, S)$ where
\begin{itemize}
\item[] $V = \underline{\phantom{FILL IN BLANK HERE}}$
\item[] $\Sigma = \underline{\phantom{FILL IN BLANK HERE}}$
\item[] $R = \underline{\phantom{FILL IN BLANK HERE}}$
\item[] $S = \underline{\phantom{FILL IN BLANK HERE}}$
\end{itemize}
\end{itemize}
{\it No justifications required for credit for this question; but, as always, they're a good idea for your own benefit.}
\end{problem}
\begin{problem}[3.] ({\bf 10 points})
\begin{itemize}
\item[a.] Suppose $M = (Q, \Sigma, \Gamma, \delta, q_0, F)$ is a PDA.
We can define a new PDA $N$ so that $L(M) = L(N)$ and $N$ is guaranteed to have an empty stack at
the end of any accepting computation. Informally, the construction is as follows:
Add three new states $q_1', q_2', q_3'$ and one new stack symbol $\#$.
\begin{itemize}
\item One of the new states $q_1'$ will be the new {\bf start} state and it has a spontaneous transition to the old start state $q_0$ which pushes the new stack symbol $\#$ to the stack.
\item The transitions between the old states are all the same.
\item From each of the old accept states, {\bf add} a spontaneous
transition (that doesn't modify the stack) to the second new state $q_2'$.
\item In this state $q_2'$, pop all old stack
symbols from the stack without reading any input.
\item When the new stack symbol $\#$ is on the top of the stack, transition to the third new state $q_3'$ and accept.
\end{itemize}
{\bf Complete the formalization of this description} by filling in the blanks
in the transition function below.
\[
N = (Q \cup \{q_1', q_2', q_3' \}, \Sigma , \Gamma \cup \{ \# \},
\delta', q_1', \{q_3' \})
\]
where we assume $\{q_1', q_2',
q_3' \} \cap Q = \emptyset$ and $\# \notin \Gamma$, and
\begin{align*}
\delta'(~(q, x, y) ~) &= \delta(~(q,x,y)~) &&\text{if $q \in Q, x \in \Sigma, y \in \Gamma_\varepsilon$} \\
\delta'(~(q,x,y) ~) &=\delta(~(q,x,y)~) &&\text{if $q \in Q, q \notin F, x = \varepsilon, y \in \Gamma_\varepsilon$} \\
\delta'(~(q,x,y) ~) &= \underline{\phantom{FILL IN BLANK HERE}}&&\text{if $q \in F, x = \varepsilon, y \in \Gamma$} \\
\delta'(~(q,x,y) ~) &= \underline{\phantom{FILL IN BLANK HERE}}&&\text{if $q \in F, x = \varepsilon, y=\varepsilon$} \\
\delta'(~(q_1', \varepsilon, \varepsilon)~) &= \underline{\phantom{FILL IN BLANK HERE}} && \\
\delta'(~(q_2', \varepsilon, x)~) &= \underline{\phantom{FILL IN BLANK HERE}}&&\text{if $x \in \Gamma$}\\
\delta'(~(q_2', \varepsilon, \#)~) &= \underline{\phantom{FILL IN BLANK HERE}} && \\
\\
\delta'(~(q,x,y)~) &= \emptyset &&\text{otherwise}
\end{align*}
{\it Some hints:
\begin{itemize}
\item The transition function of the PDA $N$ has domain
\[
Q \cup \{q_1', q_2', q_3' \} \times \Sigma_\varepsilon \times (\Gamma \cup \{ \# \})_{\varepsilon}
\]
and codomain
\[
\mathcal{P}( ~Q \cup \{q_1', q_2', q_3' \} \times (\Gamma \cup \{ \# \})_{\varepsilon}~).
\]
Make sure the outputs you specify when you fill in the blank are {\bf sets} of {\bf ordered pairs} of the right type.
\item The new machine $N$ has only one accept state: the new state $q_3'$ (where do you see this in the formal definition?).
\end{itemize}
}
\item[b.] Suppose $G = (V, \Sigma, R, S)$ and define the new grammar $G' = ( V, \Sigma, R \cup \{ S \to SS \} , S)$.
\begin{itemize}
\item[i] {\bf True} or {\bf False}: $L(G') = L(G) \circ L(G)$ {\it for all grammars $G$}.
\item[ii] {\bf True} or {\bf False}: $L (G') = ( L(G) )^*$ {\it for all grammars $G$}.
\item[iii] {\bf True} or {\bf False}: $L (G') = DOUBLE ( L(G) )$ {\it for all grammars $G$}.
\end{itemize}
\end{itemize}
{\it No justifications required for credit for this question; but, as always, they're a good idea for your own benefit.}
\end{problem}
\end{document}