Assignment II

Due date Sep. 30.

Recall that a finite state automaton (FA) is described by a quintuple:

a) An alphabet of symbols: Sigma.

b) A set of states Q.

c) A distinguished start state q0 in Q.

d) A set of accepting states F, which is a subset of Q.

e) A transition function Tr defined over Q * Sigma.

If all entries in Tr has the form Q * Sigma => Q, it maps a state and a symbol into a state, and we say that the automaton is deterministic (DFA)

If some entries in Tr has the form Q * Sigma => 2^Q (the power set of Q), then Tr maps a state and a symbol into a set of states, and we say the automaton is non-deterministic. If the automaton includes transitions where the symbol is epsilon (the empty string) we also say that the automaton is non-deterministic (NFA).

There is a simple algorithm to transform an NFA into a DFA, known as the subset construction. In a nutshell, given the set of states of the NFA, each state of the corresponding DFA corresponds to a subset of that set. Any DFA state that includes an accepting state of the NFA is an accepting state of the DFA. The transition function for the DFA is obtained from the transition function of the NFA according to the rule:

Delta-D (q-d, a) = Union (Delta-N (q, a)) where the union is over all NFA states that appear in the DFA state q-d. (If this is not familiar you might want to review the description in any standard text on formal languages or Theory of Computation).

Your assignment is to build a system that uses this algorithm. In addition to the algorithm itself, you need Inpout and output facilities. Your program should consist of three or four packages (at least): one for set manipulation, one for the algorithm, and one for I/O.

THe quintuple that describes an automaton is described as follows:

a) The alphabet is a string of characters, eg. "01". Epsilon is represented by '-' (a dash).

b) The states are numbered from 0 to N. 0 is always the start state.

c) The accepting states are given by a set of states, i.e. integers: {5, 7, 19}

d) Transitions are given with the syntax:

(state, symbol) => list_of_states.

For this assignment you can represent sets as lists or boolean vectors, whatever seems most appropriate and/or economical. The driver program should read one or more NFA descriptions, and print the corresponding DFA. I will provide some simple example to test your code.