\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor,multicol}
\usepackage{varwidth, hyperref}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Homework 4}
\duedate{Due: Monday May 8, 2017}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
Upload a {\bf single file} to Gradescope for each group.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
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 1.4, 2.1, 2.2
\newline
{\sc Key Concepts} Non regular languages, Pumping Lemma, 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 6 points}) Let $M = (Q, \Sigma, \delta, q_0, F)$ be a
DFA. Let $w = b_1 b_2 \cdots b_n$ be a string accepted by $M$ (where each
$b_i \in \Sigma$). Let $r_0, r_1, \ldots, r_n$ be the sequence of states
in the computation of $M$ on $w$. Suppose that $r_i = r_j$ for some $i$ and $j$
where $0 \leq i < j \leq n$. Prove that $L(M)$ is infinite.
\end{problem}
\begin{problem}[2.] ({\bf 10 points}) Let $N$ be a NFA with $k$ states that
recognizes some language $X$.
\begin{itemize}
\item[(a)] Show that if $X$ is nonempty, then $X$ contains some string
of length at most $k$.
\item[(b)] Show that if $\overline{X}$ is nonempty, then $\overline{X}$ contains
some string of length at most $2^k$.
\end{itemize}
{\it Extension - not for credit}: Why doesn't the bound $k$ work for $\overline{X}$?
\end{problem}
\begin{problem}[3.] ({\bf 7 points})
A common misconception about regular languages is that
if a language is regular, then its subsets or supersets must be too. In this
question, you will show that this is false. Let $\Sigma = \{ 0,1\}$.
\begin{itemize}
\item[(a)] Give an example of a regular language
$X$ that is a subset of {\bf all} nonregular languages over $\Sigma$.
Briefly justify your answer.
\item[(b)] Give an example of a regular language
$A$ and a nonregular language $B$ such that $A \subseteq B$.
For this part, you must choose $A$ and $B$ that are neither equal to
$\emptyset$ nor to $\Sigma^*$.
\item[(c)] Give an example of a nonregular language
$C$ and a regular language $D$ such that $C \subseteq D$.
For this part, you must choose $C$ and $D$ that are neither equal to
$\emptyset$ nor to $\Sigma^*$.
\end{itemize}
For each part of this problem, justify any claims you make about certain sets
being regular or nonregular either by proving the claim from definitions or
citing a fact proved in class or in the textbook.
\end{problem}
\begin{problem}[4.] ({\bf 12 points})
Consider the language
\[
\{ wtw^{\mathcal{R}} \st w\in \{0,1\}^*, t \in \{1\}^*, ~\text{and both $w, t$ are nonempty}\}.
\]
\begin{itemize}
\item[(a)] Prove that this language is not regular.
\item[(b)] Prove that this language is context-free by providing a CFG with eight
or fewer productions that generates it. Informally explain why the CFG
you provide works. {\it Note: the abbreviation $A \to 0A1 ~|~ B$ counts as
two productions.}
\end{itemize}
\end{problem}
\end{document}