\documentclass[12pt]{article}

\usepackage{tikz}
\usetikzlibrary{automata,positioning,arrows}

\newcommand{\es}{\emptyset}

\begin{document}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\centerline{\bf Homework 3 Morally Due Feb 19}

\centerline{\bf THIS HOMEWORK IS TWO PAGES LONG!!!!!!!!!!!!!!!}

\begin{enumerate}
\item
(30 points)
The alphabet is $\{a,b\}$.
Let $n \ge 0$ and let
$$L_n = \{a,b\}^*a\{a,b\}^n$$
(so the $(n+1)$th letter from the end is $a$).
\begin{enumerate}
\item
(15 points)
Draw a DFA for $L_n$ when $n=2$.
Describe the DFA for $L_n$ for any general $n$.
How many states does $L_n$ have in general as a function of $n$?
\item
(15 points)
Draw an NFA for $L_n$ for any general $n$.
You may use DOT DOT DOT and
other shortcuts.
How many states does it have as a function of $n$?
\item
(0 points)
THINK ABOUT proving that any DFA for $L_n$ has LOTS of states.
\end{enumerate}

\item
(30 points)
Use the conventions about representing numbers and sets
established in class.
Your DFA's should have ACCEPT states (labelled A),
REJECT states (labelled R), and STUPID states (labelled S).
\begin{enumerate}
\item
(15 points)
Draw a DFA for  
$$\{(x,A) \mid x+1\in A \}$$
How many states does it have?
\item
(15 points)
For all $n$ draw a DFA (you may use DOT DOT DOT) for
%How many states does it have.
$$L_{n} = \{(x,A) \mid x+n\in A \}$$
How many states does it have as a function of $n$?
\end{enumerate}

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(20 points)
Note that $47\times 101= 4747$.
Let
$$L = \{ a^n \mid n\not\equiv 0 \pmod{4747} \}.$$
There is clearly a DFA for $L$ with 4747 states.
\begin{enumerate}
\item
(10 points) Prove that ANY DFA for $L$ has to have $\ge 4747$ states.
\item
(10 ponts) Prove or Disprove: There is an NFA for $L$ with $<4747$ states.
\end{enumerate}

\item
(20 points)
Write psuedo code for an algorithm that will, GIVEN a DFA $M$ determine if
$L(M)\ne \emptyset$ or not.
(Here, $L(M)$ denotes the language that $M$ accepts.)
It must be completely self-contained, so you can't say something like
{\it Use Kruskal's MST algorithm here and pay Clyde's Uncle Joe the Royalties}
in the algorithm (HINT: that is not part of any correct answer that I know of anyway.)

\end{enumerate}
\end{document}