\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{verbatim}
\usepackage{utf8}

\begin{document}

\topic{Automata}
\homework{6}

\maketitle

\paragraph{Note:}
To show that the language of a DFA (or NFA) $M$ is $L$, you must show that for
all $x \in \Sigma^*$, $M$ accepts $x$ \textbf{if and only if} $x \in L$.
Alternatively, you can show that if $x \in L$ then $M$ accepts $x$, and if $x
\notin L$ then $M$ does not accept $L$ (this is equivalent).

\bigskip

\begin{exercises}
\item
\begin{enumerate}
\item Draw the state/transition diagram for a DFA with a binary alphabet which
recognizes the set of strings in which every sequence of three successive bits
contains a 0. {\bf Note:} the sequences of three successive characters in the
string $a_1a_2a_3a_4a_5\cdots$, are $a_1a_2a_3$, $a_2a_3a_4$, $a_3a_4a_5$ etc.

\item Explicitly write the five components of this DFA.
\end{enumerate}

\item
\begin{enumerate}
\item Let language $L$ be recognized by a DFA with $n$ states. Prove that the
language $\Sigma^* \setminus L$ (the complement of $L$, containing all strings
not in L) is also recognized by some DFA with $n$ states.

\item
Does your construction from (a) work for NFAs as well?  If not, give a
counterexample.

\item
Prove that if a language $L$ is recognized by an NFA, then
$\Sigma^* \setminus L$ is recognizable by an NFA.
\end{enumerate}

\item
Let language $L$ be recognized by a DFA, and $b$ be an arbitrary symbol
of its alphabet. Prove that the following language is also recognized by a DFA:
\begin{displaymath}
\textrm{Spaced}(L) = \{ a_1 b a_2 b a_3 b \dots b a_n \mid a_1 a_2 a_3 \dots a_n \in L \}
\end{displaymath}
{\bf Note:} Strings with just one symbol remain unchanged after ``spacing''.

\item The {\em factorial} of a natural number $n$, written $n!$, is the number
$1 \cdot 2 \cdot 3 \cdot \dots \cdot (n - 1) \cdot n$.
Prove that the language $L = \{a^{n!} \mid n \in \mathbb{N}\}$
is not recognized by any finite automaton (Hint: prove and use
the fact that for any $n$, there exists some $k$ such that $k! +
n < (k+1)!$).
\end{exercises}

\end{document}
