\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 3}
\duedate{Due: Tuesday May 1, 2018 at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW3} 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 Section 1.4, 2.2
\newline
{\sc Key Concepts} Nonregular languages, pumping lemma, pushdown automata.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]({\bf 10 points}). The alphabet for this question is $\Sigma = \{0,1\}$.
Consider the following sets.
\[
A_1 = \emptyset \qquad A_2 = \Sigma^* \qquad \qquad A_3 = \{0^n 1^n \st n \geq 0\}
\]
Fill in each blank below with $A_1$, $A_2$, or $A_3$ to make the statement true, or write ``None of the above" if none of these sets do. (If multiple choices work, you only need to give one of them for full credit.)
\begin{enumerate}
\item[a.] $DOUBLE(\underline{\phantom{BLANK}})$ is regular.
\item[b.] $DOUBLE(\underline{\phantom{BLANK}})$ is nonregular.
\item[c.] $STUTTER(\underline{\phantom{BLANK}})$ is regular.
\item[d.] $STUTTER(\underline{\phantom{BLANK}})$ is nonregular.
\item[e.] $STUTTER(\underline{\phantom{BLANK}}) = \Sigma^*$.
\end{enumerate}
The definitions for these operations are the same we've worked with before: For $L$ a set of strings, we can define the following associated sets
\[
DOUBLE(L) = \{ vv \st v \in L \}
\]
\[
STUTTER(L) = \{ w_1 w_1 w_2 w_2 \cdots w_n w_n \st n \geq 0, w_i \in \Sigma \text{ for each $i$ where $1 \leq i \leq n$, and }
w_1 w_2 \cdots w_n \in L \}
\]
Note: $\varepsilon$ is in each of these sets iff it is an element of $L$ itself.\\
{\it No justifications required for credit for this question; but, as always, they're a good idea for your own benefit.}\\
{\it Extension (not for credit)}: Do any of the examples you saw above prove whether the statement ``The class
of regular languages is closed under $DOUBLE$" is true or false? How about whether the statement ``The class
of nonregular languages is closed under $DOUBLE$" is true or false?
\end{problem}
\begin{problem}[2.] ({\bf 10 points}). We say that a string $s$ in language $L$ {\bf can be pumped in $L$} to mean
that there exist $x,y,z$ such that $s = xyz$, $|y| > 0$, and for each $i \geq 0$, $xy^iz \in L$. {\it Notice that we don't have item
3 from Theorem 1.70 because we have not fixed a $p$.} For each of the strings and languages below,
determine if the string can be pumped in the language. If so, give an example of $x, y, z$ that work for this string.
\begin{itemize}
\item[a.] $s = 110010$, $L = \{ 110010 \}$.
\item[b.] $s = 111000$, $L = L (1^* 0^*)$.
\item[c.] $s = 100$, $L = L ( 100 \cup 0^* 1^* )$.
\item[d.] $s = \varepsilon$, $L = \{0,1\}^*$.
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Consider the PDA over the input alphabet $\Sigma = \{0,1\}$ with the state diagram
\begin{center}
\includegraphics[width=5in]{PDA_HW3.png}
\end{center}
\begin{itemize}
\item[a.] What is the stack alphabet, $\Gamma$, for this PDA?
\item[b.] From which states might a computation of this PDA make a move that doesn't consume input and
doesn't push anything onto the stack?
\item[c.] From which states might a computation of this PDA make a move that doesn't change the contents of the stack?
\item[d.] At the end of a successful computation of this PDA on a string $w$, can the stack be nonempty?
\item[e.] Is the string $\varepsilon$ accepted by this PDA?
\item[f.] Is the string $01$ accepted by this PDA?
\item[g.] Is the string $110$ accepted by this PDA?
\item[h.] Is the string $0110$ accepted by this PDA?
\item[i.] For all strings $w$, if $w$ is accepted by this PDA, is $w^{\mathcal{R}}$ guaranteed to be
accepted by the PDA as well?
\item[j.] Is the language of this PDA infinite?
\end{itemize}
\end{problem}
\end{document}