FMCS Assignment #2    (due on Monday, 15 Sept 2003).
------------------

Implement a DFA minimization algorithm (for instance the algorithm
from Kozen which we did in class).  Your program should take a DFA
in a text format specified below, and output (on standard output)
the minimized DFA, in the same format.

Input format:

States are represented by numbers 0 to (n-1) where n is the total
number of states.  State '0' is the initial state.  Symbols are
represented by first k characters from [a-z] where 'k' is the number
of symbols.

Syntax of input (also syntax of output):

Line 1:
<no of states> <no of symbols> <no of final states>

e.g.
4 3 2   ==> DFA has four states, Q = {0, 1, 2, 3}. 
Its alphabet A = {a, b, c}.  It has 2 final states

Line 2:
[[[final-state1] final-state2] ... ]

e.g.
0 2	==> Final States F = {0, 2}. (blank line if |F| = 0)


Line 3 onwards (n * k lines):
<from state> <symbol> <to state>

e.g.
0 a 1 ==> DFA has a transition from State '0' to State '1' on symbol 'a'


Example: DFA for a*.b in the above specified format is:

3 2 1
1
0 a 0
0 b 1
1 b 2
2 a 2
1 a 2
2 b 2


Graphical tools to view your automata:

You can use the "Graphviz" tool to view automata in graphical
format. Here's how:

1. Use Arun's script (todot.pl) to translate the DFA format above to
the ".dot" format used by Graphviz.

$ todot.pl < a-star-b.dfa

This will output the DFA in "a-star-b.dfa", in the ".dot"
format, on standard output.

You can save this in a file "a-star-b.dot" using:

$ todot.pl < a-star-b.dfa > a-star-b.dot


2. Use the Graphviz tool "dot" to translate "a-star-b.dot" to a
   PostScript format:

$ dot -Tps a-star-b.dot > a-star-b.ps


3. View "a-star-b.ps" using a PostScript viewer like "gv":

$ gv a-star-b.ps

As a shortcut, you could use:

$ cat a-star-b.dfa | todot.pl | dot -Tps | gv - 


"todot.pl" can be downloaded from the FMCS page, and "Graphviz" is
installed on the Computing Lab and Litec machines. It can also be
downloaded and installed from
http://www.research.att.com/sw/tools/graphviz/.

Mail your solutions (source code) to Arun (faju@csa.iisc.ernet.in)
with a copy to me.

---------------