Problem Set 1 latex source
This file is provided to help students create their solutions
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\textbf{Instructions:} Read the rules for collaboration, course bibles,
etc., on the Course Information sheet (see the course homepage).
Submit your solutions on Gradescope as described on the homepage.
Usually, we will have presented all the material you need to solve
each problem set by a week before its deadline.
Read all of Chapters 1 and 2 except Section 2.4.
\item[0.1] Read and solve, \underline{but do not turn in}: Book, 1.14 .
\ [Swapping NFA accept/non-accept states]
\item[0.2] Read and solve, \underline{but do not turn in}: Book, 1.31 .
\ [Closure under reversal]
\item[0.3] Read and solve, \underline{but do not turn in}: Book, 1.46b .
\ [Pumping lemma]
\item[0.4] Read and solve, \underline{but do not turn in}: Book, 2.4 and 2.5 .
\ [Practice with \cfls] \\
Note, problems marked with ${}^\mathsf{A}$ have solutions at the end
of the chapter.
You may assume the solutions to the above problems when
solving the problems below.
\item
For every $b \ge 2$, let $\SS_b=\{\st0,\st1,\ldots,b-1\}$
where each member of $\SS_b$ is considered to be a single symbol.
Consider a string $s\in\SS_b^*$ to be a number written in base $b$.
The empty string represents the number 0.
Let $\lang{MFIVE}_b=\set{s\in\SS_b^*}{s}$ represents some multiple of
5 in base $b$\setend.
For example, $\st{1010}\in \lang{MFIVE}_2$ and $\st{120}\in
\lang{MFIVE}_3$ and $\st{45}\in \lang{MFIVE}_{10}$.
\begin{enumerate}
\item Show that $\lang{MFIVE}_3$ is regular by giving the state diagram
of a \dfa\ $M_3$ that recognizes it. (Hint: Simulate long division. You
need only 5 states.)
\item Show that $\lang{MFIVE}_d$ is regular for each $d\ge 2$ by giving
the formal description of a \dfa\ $M_d$ that recognizes it.
\end{enumerate}
\item
The \emph{Hamming distance} $H(x,y)$ between two strings $x$ and $y$ of
equal length, is the number of corresponding symbols at which $x$ and $y$
differ. For example, $H(\st{1101111}, \st{0001111}) =2$.
For any language $A$,
let $N_1(A)= \set{w} H(w,x) \le 1$ for some $x\in A\setend$. \\
Show that the class of regular languages is closed under the $N_1$ operation.
\item
Let $D=\set{w}w\in\{\st0,\st1\}\kstar$ is not a palindrome
(i.e., $w\neq w^{\mathcal R}$)\setend.
Prove that $D$ is not regular.
\item
Let $\SS=\{\st0,\st1\}$.
\begin{enumerate}
\item Let $\lang{TUT}=\set{tut} t,u\in\SSS\setend$.
Show $\lang{TUT}$ is regular.
\item Let $\lang{TUTU}=\set{tutu} t,u\in\SSS\setend$.
Show $\lang{TUTU}$ is not regular.
\end{enumerate}
\item
Let $x$ and $y$ be strings over some alphabet $\SS$.
Say $x$ is a \defin{substring} of $y$ if $y\in\SSS x \, \SSS$. \\
Define the \defin{avoids} operation for languages $A$ and $B$ to be
$$
A \text{\lang{ avoids }} B = \set{w}w\in A \text{ and $w$
doesn't contain any string in $B$ as a substring}\setend.
$$
Show that the class of regular languages is closed under
the \emph{avoids} operation. \\
(Hint: Theorems we've previously shown may be helpful.)
\item
Let $M_1$ and $M_2$ be \dfas\ that have $k_1$ and $k_2$ states,
respectively, where $L(M_1) \neq L(M_2)$.
Using an argument similar to the proof of the pumping lemma, show that
there is a string $s$ where $|s| \leq k_1 k_2$ and where exactly
one of $M_1$ and $M_2$ accepts $s$.
\item[$7.^{\!\star}$] ($\star$ means optional)
Improve the bound in Problem 6 to show that such an $s$ exists
where $|s|\leq k_1+k_2$.