\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 3}
\duedate{Due: Saturday May 5, 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 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})
\begin{itemize}
\item[a.] Use Pumping Lemma to prove that $DOUBLE( \{ 0^n 1^n \st n \geq 0 \} )$ is nonregular.
\item[b.] Explain the problem in the following attempted proof that $STUTTER ( \{ 0^n 1^n \st n \geq 0 \}) $ is nonregular:
\begin{quote}
``Proof": In class, we proved that the language $\{0^n 1^n \st n \geq 0 \}$ is nonregular. In GroupHW1 we proved that
the class of regular languages is closed under the operation $STUTTER$. Applying the contrapositive of this closure claim,
we see that $STUTTER(\{0^n1^n \st n \geq 0 \})$ must be nonregular as well.
\end{quote}
{\it Extension (not for credit): How would you prove that $STUTTER(\{0^n1^n \st n \geq 0 \})$ is nonregular? }
\item[c.] Let $L$ be any nonregular set and $L_F$ be any finite set. Prove that $L \cup L_F$ is nonregular too.
{\it Hint: do not use Pumping Lemma.}
\item[d.] Prove that you can't replace union with intersection in the claim above. That is, give an example of a specific
nonregular set and a specific finite set whose intersection is regular.
\end{itemize}
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) For this problem, assume $L$ is a regular language with pumping length $5$.
Briefly justify your answers to each of the following True/False questions.
\begin{itemize}
\item[a.] True / False: $L$ has pumping length $10$.
\item[b.] True / False: All strings in $L$ have length less than or equal to $5$.
\item[c.] True / False: If there is a string in $L$ with length equal to $4$, then $L$ is finite.
\item[d.] True/ False: If there is a string in $L$ with length equal to $6$, then $L$ is infinite.
\end{itemize}
\end{problem}
\begin{problem}[3.] ({\bf 10 points}) Design a PDA over the alphabet $\{a,b,c \}$ that
recognizes the set of all palindromes. In other words, the language of your PDA should be
\[
\{ w \in \{a,b,c\}^* \st w = w^\mathcal{R} \}
\]
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.\\
{\it Hint: Make sure to take into account both odd and even length palindromes; you might find Example 2.18 in the
book helpful, as well as question 3 in the Individual HW.}
\end{problem}
\end{document}