More user feedback on Sets.py

[David Eppstein]

In article <Rxlrb.6067$hB5.3380 at nwrdny02.gnilink.net>,
 "Raymond Hettinger" <vze4rx4y at verizon.net> wrote:

> > For something concrete (that I thought about doing recently but haven't
> > actually done): conversion of NFA to DFA and then state minimization of
> > the resulting DFA.  The converted DFA's states are sets of states of the
> > NFA, and the state minimization involves sets of DFA states.
> 
> That would be a perfect way to test drive the sets module.

Here is the first half of this.  I didn't do the state minimization 
part.  (For the example shown here, the output is already minimal.)

"""automata.py
Convert nondeterministic to deterministic finite automata.

D. Eppstein, UC Irvine, November 2003.
"""

from __future__ import generators
from sets import ImmutableSet,Set

if 'True' not in globals():
    globals()['True'] = not None
    globals()['False'] = not True

class InputError(Exception): pass

class DFA:
    def __init__(self,Sigma,delta,S0,F):
        """Create deterministic finite automaton with alphabet Sigma,
        transition function delta(state,letter)->state, initial state
        S0, and predicate F(state)->boolean. The full sets of states and
        final states are determined implicitly from the delta and F
        functions.
        """
        self.alphabet = ImmutableSet(Sigma)
        self.transition = delta
        self.initialState = S0
        self.isfinal = F

    def states(self):
        """Generate all states of the DFA."""
        explored = Set()
        unexplored = Set([self.initialState])
        while unexplored:
            s = unexplored.pop()
            explored.add(s)
            yield s
            for c in self.alphabet:
                t = self.transition(s,c)
                if t not in explored:
                    unexplored.add(t)

    def __call__(self,input):
        """Test whether input is accepted by the DFA."""
        state = self.initialState
        for c in input:
            if c not in self.alphabet:
                raise InputError("Symbol " + repr(c) +
                                 " not in input alphabet")
            state = self.transition(state,c)
        return self.isfinal(state)

class NFA:
    def __init__(self,Sigma,delta,S0,F):
        """Create nondeterministic finite automaton (without
        epsilon-transitions). Arguments are the same as for a
        deterministic finite automaton, except that the initial state
        and result of the transition function are both sets.
        """
        self.alphabet = ImmutableSet(Sigma)
        self.transition = delta
        self.initialStates = ImmutableSet(S0)
        self.isfinal = F

    def setTransition(self,states,c):
        """States reachable from input set by input c."""
        result = Set()
        for s in states:
            result |= self.transition(s,c)
        return ImmutableSet(result)
        
    def finalSet(self,states):
        """Test whether any of given set of states is final."""
        for s in states:
            if self.isfinal(s):
                return True
        return False

    def makeDeterministic(self):
        """Convert NFA to DFA."""
        return DFA(self.alphabet,self.setTransition,
                   self.initialStates,self.finalSet)

    def __call__(self,input):
        """Test whether input is accepted by the NFA."""
        return self.makeDeterministic()(input)

# Example from Sipser, _Introduction to the Theory of Computation_
# (Preliminary Edition), Example 1.13, pages 47-48
if __name__ == "__main__":

    # state:(states for transition on 0, states for transition on 1)
    Sipser_1_13 = {
        1: ([1], [1,2]),
        2: ([3], [3]),
        3: ([4], [4]),
        4: ([], []),
    }
    def delta(s,i): return ImmutableSet(Sipser_1_13[s][int(i)])
    def final(s): return s == 4
    N2 = NFA("01",delta,[1],final)
    
    def test(input):
        print input,(N2(input) and "is" or "is not"),"in L(N2)"
    test("000100")
    test("0011")
    
    print
    print "Conversion to DFA:"
    print
    D2 = N2.makeDeterministic()
    for s in D2.states():
        print s
        for c in "01":
            print "  --[" + c + "]-->", D2.transition(s,c)

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science