\ifx\AllTogetherMode\undefined%
\IfFileExists{../prefix.tex}%
{\input{../prefix}}%
{\input{prefix}}%
\fi
\OLDHomeworkStart%
{3} % Homework number
{4} % Week of semester submitted
{1.1} % Version
\SaveIndent%
\begin{questions}[start=7]
\RestoreIndent%
\medskip%
\item \OLDHWProblem{100}{Draw me a sheep.}{%
For each of the following languages, draw (or describe
formally) an \NFA that accepts them. Your automata should have
a small number of states. Provide a short explanation of your
solution, if needed.
\begin{questions}%[(A)]
\item All strings over $\{ \T{a}, \T{b}, \T{c}\}^*$
in which every nonempty maximal substring of consecutive
\T{a}s is of even length.
\item
$\Sigma^* \T{a} \Sigma^* \T{b}
\Sigma^*\T{c}\Sigma^*$.
\item
$\pth{\T{a}(\T{a} + \T{b})^*\T{a} + \T{b}(\T{b}
+ \T{c})^*\T{b} + \T{c}(\T{c} + \T{a})^*
\T{c}}^*$.%
\item
$\pth{\pth{(\T{aa}+\T{aab})^*(\T{bab}+\T{bb})^* +
\T{c} \bigl.} \Bigl. \T{b}}^* + \T{bb}$.
\item All strings in $\T{1}^*$ of length that is
divisible by at lease one of the following numbers
$2,3,5,7$. For full credit your automata should have less
than (say) 20 states.
\item All strings in $\T{a}^*$ of length that is
NOT divisible by any of the following numbers
$2,3,5,7$.
\end{questions}
}{}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip%
\item \OLDHWProblem{100}{Blip b{lo}p.}{%
\medskip%
For two binary strings $x,y \in \{ \T0, \T1\}^*$, of the
same length, their \emphi{Hamming distance} $d_H(x,y)$ is the
number of bits in which they differ. For example
$d_H(\T{1111},\T{1111}) = 0$,
$d_H(\T{0001},\T{1111}) = 3$, and
$d_H(\T{1111001},\T{1111011}) = 1$. As a negative example,
observe that $d_H(\T{11},\T{1011})$ is not defined.
Let $L \subseteq \{ \T0, \T1\}^*$ be a regular language.
\begin{questions}%[(A)]
\smallskip%
\item Consider the language
$L_{\leq 1} = \Set{x \in \{ \T0, \T1\}^*}{ \exists y
\in L \text{ s.t. } d_H(x,y) \leq 1}$. Describe in words
what the language $L_{\leq 1}$ is.
\item Consider the following \DFA $M$.
\centerline{\includegraphics[width=0.4\linewidth]%
{\File{figs/dfa_q_1}}}
What is its language $L=L(M)$?
\smallskip
\item By modifying the given \DFA give above, describe an
\NFA that that accepts the language $L_{\leq 1}$. Explain
your construction.
\smallskip%
\item More generally, demonstrate that if a language
$L \subseteq \{ \T0, \T1\}^*$ is regular, then
$L_{\leq 1}$ is a regular language (for simplicity, you can
assume $\eps \notin L$). Specifically, consider a \DFA for
$L$, and describe in detail how to modify it to an \NFA for
$L_{\leq 1}$. (The description of the \NFA does not have
to be formal here.) Explain why the constructed \NFA
accept the desired language.
\smallskip%
\item Prove, that for any constant $k$, the language
$L_{\leq k}$ is regular. Your proof has to be formal and
provide all necessary details. (I.e., you need to provide
an explicit formal description of the resulting \NFA for
the new language, and prove that the \NFA accepts the
language $L_{\leq k}$).
\end{questions}
}{}{}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bigskip%
\item \OLDHWProblem{100}{Codes.}{%
Let $\Sigma$ be finite alphabet. A \emphi{code} is a mapping
$f:\Sigma \rightarrow \brc{\T0,\T1}^+$. For example, if
$\Sigma = \brc{ \T{a}, \T{b},\T{c}}$, a code $f$ might be
$f( \T{a}) = \T{00010}$, $f( \T{b}) = \T{000}$, and
$f( \T{c}) = \T{1}$. (To simplify things, we assume that
$f(a) \neq \eps$, for any character $a \in \Sigma$.)
For a string $w_1 w_2 \cdots w_m \in \Sigma^*$, we define $f(w)
= f(w_1) f(w_2) \cdots f(w_m)$. In the above code, we have
\begin{align*}
f( \T{abcba})%
=%
\T{00010}%
\Cdot%
\T{000} %
\Cdot%
\T{1}%
\Cdot%
\T{000} %
\Cdot%
\T{00010}.
=
\T{00010}%
\T{000} %
\T{1}%
\T{000} %
\T{00010}.
\end{align*}
\medskip%
\begin{questions}%[(A)]
\item \points{10} Let $L$ be the language of the following
\DFA $M$. What is $L$?
\centerline{\includegraphics[scale=0.35]%
{\File{figs/dfa}}}%
\item \points{20} Working directly on the \DFA $M$ from (A)
construct an \NFA for the language $f(L)$. Here
$f(L) = \Set{f(w)}{w \in L}$ is the \emph{code
language}. Where $f$ is code from the above example.
\medskip%
\item \points{30} Let $L \subseteq \Sigma^*$ be am
arbitrary regular language. Prove that the encoded language
$f(L) = \Set{f(w)}{w \in L}$ is regular.
\medskip%
Specifically, given a \DFA $M = (Q, \Sigma, \delta, s, A)$
for $L$, describe how to build an \NFA $M'$ for
$f(L)$. Give an upper bound on the number of states of
$M'$.
(I.e., You need to prove the correctness of your
construction -- that the language of the constructed \NFA
is indeed the desired language $f(L)$.)
(Rubric: Half the credit is for a correct construction, and
the other half is for a correct proof of correctness.)
\medskip%
\item \points{40} Let $L \subseteq \brc{\T0,\T1}^*$ be a
regular language. Consider the decoded language
$L_f = \Set{ w \in \Sigma^*}{f(w) \in L}$.
Prove that $L_f$ is a regular language. As above, given a
\DFA $M$ for $L$, describe how to construct an \NFA for
$L_f$.
(Rubric: Half the credit is for a correct construction, and
the other half is for a correct proof of correctness.)
\end{questions}
}{}{}{}
\end{questions}
\HomeworkEnd{}