\documentclass{article}

%
% title macros
%
\newcommand\myname{Prof. Nadeem Abdul Hamid}
\newcommand\course{CSC 320 Spring 2005}
\newcommand\hwnum{3}
\newcommand\duedate{Monday, February 21, 2005}

\newcommand\probtitle{
 \title{Homework \hwnum\ --\ Due: \duedate}\author{\myname\\\course}\date{}
 \maketitle}
\newcommand\solntitle{
	{\bf\flushright \myname\\\course\\\today\\Homework \hwnum\\}}


%
% local macros
%
\newcommand\powset[1]{\mathcal{P}(#1)}
\newcommand\problem{\section{}}



%
% main document
%
\begin{document}

\probtitle 


\problem 
Write a computer program taking as input a DFA, $M = (Q, \Sigma, \delta, q_0, F)$ and a string $w$ and returning the sequence of states traversed along the path specified by $w$ (from the start state). The program should also indicate whether or not the string $w$ is accepted. Use the format described below for the input and the output:

Assume that the states are the integers $1, 2, \ldots, n$, where $n$ is the total number of states, the start state being state $1$, and that the input symbols are the first $m$ lower-case letters of the English alphabet (a, b, c, \ldots), with $1 \leq m \leq 26$. The transition table will be specified as an $n \times m$ matrix (the rows indexed by states and columns indexed by input symbols) where the entry in row $i$ and column $j$ is $\delta(i,j)$ i.e., the target of the transition from state $i$ on input $j$. The input file will consist of the data in the following order:

\[\begin{array}{l}
n \\
m \\
\delta(q_1, a_1)\ \ \delta(q_1, a_2)\ \ldots\ \ \delta(q_1, a_m) \\
\delta(q_2, a_1)\ \ \delta(q_2, a_2)\ \ldots\ \ \delta(q_2, a_m) \\
\ldots\ \ldots\ \ldots\\
\delta(q_n, a_1)\ \ \delta(q_n, a_2)\ \ldots\ \ \delta(q_n, a_m) \\
F\ \  \textrm{(number of final states)}\\
f_1\ \ f_2\ \ f_3\ \ldots\ \ f_F \\
w_1\,w_2\,w_3\,\ldots w_k\ \ \textrm{(the input string)}\\
\end{array}\]

Your program should read in such an input file and output to the screen the sequence of states that the DFA traverses and whether it accepts or rejects. You may assume that the input file is in the right format, so you do not have to worry about error handling. 
\clearpage
Here is a sample input file \verb+input.txt+:

\begin{verbatim}
3
2
2 3
2 3
3 3
1
3
abbbaaabbababa \end{verbatim}

Here is a sample of the output your program might produce for the above input file:

\begin{verbatim}
$ java DFASim input.txt

Number of states: 3
Alphabet: ab
Transitions:
   d(1, a) = 1
   d(1, b) = 2
   d(2, a) = 1
   d(2, b) = 2
   d(3, a) = 2
   d(3, b) = 2
Final states:
   3
Input: abbbaaabbababa
Going to: 2
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
Going to: 3
ACCEPT  \end{verbatim}

\emph{(Problem adapted from Jean Gallier)}



\problem
Answer exercise 1.16, both parts (a) and (b), in the textbook (page 86).

\problem
Answer exercise 1.17, part (a) only: Use the pumping lemma to show that the following language is not regular:\\
$A_1 = \{ 0^n1^n2^n | n \geq 0 \}$.

\problem
Answer problem 1.41, page 90 in the textbook. Let
\[ D = \{ w\ |\ w\ \textrm{contains an equal number of occurrences of the substrings 01 and 10}\ \}.\]
Show that $D$ is a regular language.

\end{document}