\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input ../adgeomcs/mac.tex
\input ../adgeomcs/mathmac.tex

\def\Hom#1#2#3{\mathrm{Hom}_{#1}(#2, #3)}
\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}
\def\buildrell#1\over#2{\mathrel{\mathop{\null#1}\limits_{#2}}}
\def\rmder#1{{\ \buildrell  \Longrightarrow \over{rm}}^{#1}\ }
\def\lmder#1{\buildrel #1\over{\buildrell  \Longrightarrow \over{lm}}}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2003 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
\vspace{0.5cm}
Homework 5a}\\[10pt]
March 27, 2003; Due April 17, beginning of class\\
\end{center}

%\vspace {0.5cm}
%``B problems'' must be turned in.


\vspace {0.25cm}\noindent
{\bf Programming Project (80 pts).}
This problem is based on the method
proved correct in Problem B4 of Homework $3$.

\medskip
Given a DFA $D = (Q, \Sigma, \delta, q_0, F)$,
for any two states $p, q\in Q$,
a fast algorithm for computing the forward closure of the
relation $R = \{(p, q)\}$, or detecting a bad pair of states,
can be obtained as follows:  An equivalence relation on $Q$ is
represented by a partition $\Pi$. Each equivalence class
$C$ in the partition is represented by a tree structure
consisting of nodes and (parent) pointers, with the
pointers from the sons of a node
to the node itself. The root has a null pointer.
Each node also maintains a counter keeping track
of the number of nodes in the subtree rooted at that node.

\medskip
Two functions $union$ and $find$ are defined as follows.
Given a state $p$, $find(p,\Pi)$ finds the root
of the tree containing $p$ as a node (not necessarily a leaf).
Given two root nodes $p, q$, $union(p, q, \Pi)$ forms
a new partition by merging the two trees with roots $p$ and $q$
as follows: if the counter of $p$ is smaller than
that of $q$, then let the root of $p$ point to $q$,
else let the root of $q$ point to $p$.

\medskip
In order to speed up the algorithm, we can modify $find$ as follows:
during a call $find(p,\Pi)$, as we follow the path from $p$ to
the root $r$ of the tree containing $p$, we redirect the parent pointer
of every node $q$ on the path from $p$ (including $p$ itself) to
$r$.

\medskip
Say that a pair $\lag p, q\rag$ is {\it bad\/} iff either
both $p\in F$ and $q\notin F$, or both $p\notin F$ and $q \in F$.
The function $bad$ is such that $bad(\lag p, q\rag) = true$ if 
$\lag p, q\rag$ is bad, and $bad(\lag p, q\rag) = false$
otherwise.

\medskip
For details of this implementation of partitions, see
{\sl Fundamentals of data structures}, by Horowitz and Sahni,
Computer Science press, pp. 248-256.

\medskip
Then, the algorithm is as follows:

\vfill\eject\noindent

\medskip
{\bf function} $unif[p, q, \Pi, dd]$: $flag$;

\smallskip
\quad 
{\bf begin}

\smallskip
\quad \quad
$trans := left(dd)$; $ff := right(dd)$;  $pq := (p, q)$; 
$st := (pq)$; $flag := 1$;

\smallskip
\quad\quad
 $k:= Length(first(trans))$;

\smallskip
\quad\quad
 {\bf while $st \not= () \land  flag \not= 0$ do}

\smallskip
\quad\quad\quad
       $uv := top(st)$; $uu := left(uv)$; $vv := right(uv)$;

\smallskip
\quad\quad\quad
       $pop(st)$;

\smallskip
\quad\quad\quad
       {\bf if $bad(ff, uv) = 1$ then  $flag := 0$}

\smallskip
\quad\quad\quad
       {\bf else} 

\smallskip
\quad\quad\quad\quad
         $u := find(uu, \Pi)$; $v := find(vv, \Pi)$;

\smallskip
\quad\quad\quad\quad
          {\bf if $u \not= v$ then}

\smallskip
\quad\quad\quad\quad\quad
                 $union(u,v,\Pi)$;

\smallskip
\quad\quad\quad\quad\quad
                {\bf for $i = 1$ to $k$ do}

\smallskip
\quad\quad\quad\quad\quad\quad
      $u1 := delta(trans,uu,k-i+1)$; $v1 := delta(trans,vv,k-i+1)$;

\smallskip
\quad\quad\quad\quad\quad\quad
      $uv := (u1, v1)$; $push(st,uv)$

\smallskip
\quad\quad\quad\quad\quad
                {\bf endfor}

\smallskip
\quad\quad\quad\quad
          {\bf endif}

\smallskip
\quad\quad\quad
     {\bf endif}

\smallskip
\quad\quad
  {\bf endwhile}

\smallskip
\quad
{\bf end}

\medskip
The initial partition $\Pi$ is the identity relation
on $Q$, i.e., it consists of blocks $\{q\}$
for all state $q\in Q$.
The algorithm uses a stack $st$.
We are assuming that the DFA $dd$ is specified
by a list of two sublists, the first list,
denoted $left(dd)$ in the pseudo-code above, being
a representation of the transition function, and the second
one, denoted $right(dd)$,  
the set of final states. The transition function itself
is a list of lists, where the $i$-th list represents the
$i$-th row of the transition table for $dd$.
The function $delta$ is such that $delta(trans,i,j)$ returns
the $j$-th state in the $i$-th row of the transition table of $dd$.
For example, we have a DFA
$$dd = (((2, 3), (2, 4), (2, 3), (2, 5), (2, 3), 
        (7, 6), (7, 8), (7, 9), (7, 6)), (5, 9))$$
consisting of $9$ states labeled $1, \ldots, 9$,
and two final states $5$ and $9$. Also, the alphabet
has two letters, since every row in the transition
table consists of two entries. For example, the two transitions
from state $3$ are given by the pair $(2, 3)$,
which indicates that $\delta(3, a) = 2$ and $\delta(3, b) = 3$. 

\medskip
Implement the above algorithm, and test it at least for the above DFA $dd$
and the pairs of states $(1, 6)$ and $(1, 7)$.
Pay particular attention to the input and output format.
Explain your data structures.

\vspace {0.25cm}\noindent
{\bf Extra Credit\/} (up to {\bf 100 pts).\/}
Implement your program in such a way that
it displays the simultaneous parallel forward moves
in the DFA, and the updating of the trees
representing the blocks of the partition.
You should produce a Java Applet.


\vspace{0.25cm}\noindent
{\bf TOTAL: 80 + 100  points.}

\end{document}