\documentclass{article}
\pagestyle{empty}

\begin{document}
\begin{center}
{\LARGE CS140: Algorithms }\\
\vspace{.1 in}
{\Large Spring 2001}\\
\vspace{.3 in}
{\large Assignment 8}
\end{center}

\noindent
This assignment is due by the start of class on Tuesday, Mar 27.  You may collaborate
with your classmates to complete this assignment but you must reference your collaborators.  In addition,
you must do your own write-up.  This assignment is worth 100 points (65 points if handwritten).  


\vspace{.2 in}
\begin{enumerate}
\item
Recall that a {\em finite automaton} is a directed graph with
edges labelled by symbols from an alphabet $\Sigma$.  In addition, one node of the
graph, $s$, is specified to be the {\em start state} and one or more nodes are specified
as accept states.  A word $w$ in $\Sigma^*$ is {\em accepted} by the DFA if there is a path
with edges labels $w$ from $s$ to some accept state. We use $L(M)$ to denote the language of
the automaton $M$; i.e.  set of
strings accepted by $M$.
 
A finite automaton is a
{\em deterministic} finite automaton ({\em DFA} if for every node $v$ in the graph and every symbol
$a \in \Sigma$, $v$ has exactly one out-edge labelled $a$.

\begin{enumerate}
\item
Draw a DFA for the language. $\{0*1\}$.
\item
Given a DFA $M$ and an integer $K$, show how to construct a DFA that
accepts exactly those string of $L(M)$ that have length $K$.
\item
Design an algorithm that takes as input the description of a DFA $M$ and an integer
$K$ and outputs the number of strings of length $K$ in $L(M)$.
(Hint:  Use inductive design, strengthening the inductive hypothesis as necessary.
Then use dynamic programming to achieve polynomial time.)
\end{enumerate}
\item
Problem 16-4 on page 326 of the text.
\item
Problem 16-5 on page 327 of the text.




\end{enumerate}
\end{document}

