[Python-checkins] python/nondist/sandbox/setobj automata.py, NONE, 1.1

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/nondist/sandbox/setobj
In directory sc8-pr-cvs1:/tmp/cvs-serv29107

Added Files:
	automata.py 
Log Message:
Demo application of sets of sets by David Eppstein.

Included in the sandbox to demonstrate the effectiveness of setobject.c 
for implementing NFA/DFA algorithms.  Exercises set.ior(), set.pop(),
set.add(), iteration, membership testing, and frozensets as members of 
both sets and dictionaries.



--- NEW FILE: automata.py ---
"""automata.py
Convert nondeterministic to deterministic finite automata.

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

try:
    from set import frozenset as ImmutableSet, set as Set
except ImportError:
    from sets import ImmutableSet, Set

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)