FSAPy/download/files/Wlist2RE.py
def makeFSA(wlist):
    """Returns a non-deterministic minimal automaton incrementally generated from a word list."""

    # store all the states and as value tuples of production and goal state
    # key: state
    # value: [ (to-state, emission-symbol), ... ]
    states = { 0:None, 1:[] }

    countstates = 1 # this number is the currently highest numbered state
    finalstates = [ 0 ] # list of final states

    # INIT: store all words as starting from startstate
    # suffixes is used as helping data structure to eliminate duplicates
    suffixes = {}
    for i in wlist:
        suffixes[i] = 1
    # tuple list: state, [suffix1, suffix2, ... ], history=(state1, state2, ...)
    agenda = [ (1, suffixes.keys(), tuple() ) ]
    suffixes = {} # empty suffixes!
    statesuffixes = {} # store all suffixes for a state

    while True:
        if len(agenda) == 0:
            break
        currentstate, suffixlist, history = agenda.pop()
        # get suffixes, if exist:
        tmpval = statesuffixes.get(currentstate, [])
        tmpval = tmpval + suffixlist
        tmpval.sort()
        statesuffixes[currentstate] = tmpval

        prefList = makePrefixList(suffixlist)
        for x in prefList.keys():
            val = prefList[x]
            if finals in val and len(val) == 1:
                    # link this to final state
                    transitions = states.get(currentstate, [])
                    if (x, 0) not in transitions:
                        transitions.append( (x, 0) )
                        states[currentstate] = transitions
                    # generate suffix and store in suffix list
                    tmpsuf = x
                    sto = currentstate
                    for i in range(len(history) - 1, -1, -1):
                        if history[i] in finalstates:
                            # only if the current state is not a final one too
                            break
                        outgoing = states[history[i]]
                        if len(outgoing) > 1:
                            break
                        for n in outgoing:
                            if n[1] == sto:
                                tmpsuf = n[0] + tmpsuf
                        sto = history[i]
                    tmp = suffixes.get(tmpsuf, -1)
                    if tmp == -1:
                        suffixes[tmpsuf] = sto
                    continue

            # if there is one suffix and it is in suffixes
            # link it to the state this suffix starts from
            if len(val) == 1 and suffixes.has_key(val[0]):
                transition = (x, suffixes[val[0]])
                transitions = states.get(currentstate, [])
                if transition not in transitions:
                    transitions.append(transition)
                    states[currentstate] = transitions
            else:
                # make new transition
                countstates += 1
                transition = (x, countstates)
                transitions = states.get(currentstate, [])
                if transition not in transitions:
                    transitions.append(transition)
                    states[currentstate] = transitions
                if finals in val:
                    if countstates not in finalstates:
                        finalstates.append(countstates)
                    val.remove(finals)
                agenda.append( (countstates, val, tuple(list(history) + [ currentstate ])) )

    # check for equal subpaths in the end
    merged = {}
    for key in statesuffixes.keys():
        val = tuple(statesuffixes[key])
        del statesuffixes[key]
        # hash table with transition and target state as key
        # and starting state as value
        # the target state converted to final vs. non-final
        if statesuffixes.has_key(val):
            # merge the states
            merged[key] = statesuffixes[val]
        else:
            statesuffixes[ max( (key, val) ) ] = min( (key, val) )
    statesuffixes = None

    # change the states that need to be merged
    for i in states.keys():
        newval = []
        oldval = states[i]
        if oldval == None:
            continue
        for j in oldval:
            if merged.has_key(j[1]):
                newval.append( (j[0], merged[ j[1] ]) )
            else:
                newval.append( (j[0], j[1]) )
        states[i] = newval

    myFSA = FSA() # new FSA

    # eliminate unnecessary states by traversing
    agenda = []
    for i in states[1]:
        agenda.append( i )
        myFSA.add(1, i[0], i[1], None, None)

    while True:
        if not agenda:
            break
        inp, state = agenda.pop()
        val = states[state]
        if val:
            for i in val:
                agenda.append( i )
                myFSA.add(state, i[0], i[1], None, None)
    # erase unnecessary data
    states = None

    existingstates = myFSA.getStates()
    for i in finalstates:
        if i in existingstates:
            myFSA.setFinal(i)
    myFSA.setFinal(0)
    myFSA.setStart(1)

    return myFSA
Returns a non-deterministic minimal automaton incrementally generated from a word list.
Returns a non-deterministic minimal automaton incrementally generated from a word list.
Returns a non - deterministic minimal automaton incrementally generated from a word list .
def makeFSA(wlist):
    states = { 0:None, 1:[] }
    countstates = 1 
    finalstates = [ 0 ] 
    suffixes = {}
    for i in wlist:
        suffixes[i] = 1
    agenda = [ (1, suffixes.keys(), tuple() ) ]
    suffixes = {} 
    statesuffixes = {} 
    while True:
        if len(agenda) == 0:
            break
        currentstate, suffixlist, history = agenda.pop()
        tmpval = statesuffixes.get(currentstate, [])
        tmpval = tmpval + suffixlist
        tmpval.sort()
        statesuffixes[currentstate] = tmpval
        prefList = makePrefixList(suffixlist)
        for x in prefList.keys():
            val = prefList[x]
            if finals in val and len(val) == 1:
                    transitions = states.get(currentstate, [])
                    if (x, 0) not in transitions:
                        transitions.append( (x, 0) )
                        states[currentstate] = transitions
                    tmpsuf = x
                    sto = currentstate
                    for i in range(len(history) - 1, -1, -1):
                        if history[i] in finalstates:
                            break
                        outgoing = states[history[i]]
                        if len(outgoing) > 1:
                            break
                        for n in outgoing:
                            if n[1] == sto:
                                tmpsuf = n[0] + tmpsuf
                        sto = history[i]
                    tmp = suffixes.get(tmpsuf, -1)
                    if tmp == -1:
                        suffixes[tmpsuf] = sto
                    continue
            if len(val) == 1 and suffixes.has_key(val[0]):
                transition = (x, suffixes[val[0]])
                transitions = states.get(currentstate, [])
                if transition not in transitions:
                    transitions.append(transition)
                    states[currentstate] = transitions
            else:
                countstates += 1
                transition = (x, countstates)
                transitions = states.get(currentstate, [])
                if transition not in transitions:
                    transitions.append(transition)
                    states[currentstate] = transitions
                if finals in val:
                    if countstates not in finalstates:
                        finalstates.append(countstates)
                    val.remove(finals)
                agenda.append( (countstates, val, tuple(list(history) + [ currentstate ])) )
    merged = {}
    for key in statesuffixes.keys():
        val = tuple(statesuffixes[key])
        del statesuffixes[key]
        if statesuffixes.has_key(val):
            merged[key] = statesuffixes[val]
        else:
            statesuffixes[ max( (key, val) ) ] = min( (key, val) )
    statesuffixes = None
    for i in states.keys():
        newval = []
        oldval = states[i]
        if oldval == None:
            continue
        for j in oldval:
            if merged.has_key(j[1]):
                newval.append( (j[0], merged[ j[1] ]) )
            else:
                newval.append( (j[0], j[1]) )
        states[i] = newval
    myFSA = FSA() 
    agenda = []
    for i in states[1]:
        agenda.append( i )
        myFSA.add(1, i[0], i[1], None, None)
    while True:
        if not agenda:
            break
        inp, state = agenda.pop()
        val = states[state]
        if val:
            for i in val:
                agenda.append( i )
                myFSA.add(state, i[0], i[1], None, None)
    states = None
    existingstates = myFSA.getStates()
    for i in finalstates:
        if i in existingstates:
            myFSA.setFinal(i)
    myFSA.setFinal(0)
    myFSA.setStart(1)
    return myFSA
def makeFSA ( wlist ) : states = { 0 : None , 1 : [ ] } countstates = 1 finalstates = [ 0 ] suffixes = { } for i in wlist : suffixes [ i ] = 1 agenda = [ ( 1 , suffixes . keys ( ) , tuple ( ) ) ] suffixes = { } statesuffixes = { } while True : if len ( agenda ) == 0 : break currentstate , suffixlist , history = agenda . pop ( ) tmpval = statesuffixes . get ( currentstate , [ ] ) tmpval = tmpval + suffixlist tmpval . sort ( ) statesuffixes [ currentstate ] = tmpval prefList = makePrefixList ( suffixlist ) for x in prefList . keys ( ) : val = prefList [ x ] if finals in val and len ( val ) == 1 : transitions = states . get ( currentstate , [ ] ) if ( x , 0 ) not in transitions : transitions . append ( ( x , 0 ) ) states [ currentstate ] = transitions tmpsuf = x sto = currentstate for i in range ( len ( history ) - 1 , - 1 , - 1 ) : if history [ i ] in finalstates : break outgoing = states [ history [ i ] ] if len ( outgoing ) > 1 : break for n in outgoing : if n [ 1 ] == sto : tmpsuf = n [ 0 ] + tmpsuf sto = history [ i ] tmp = suffixes . get ( tmpsuf , - 1 ) if tmp == - 1 : suffixes [ tmpsuf ] = sto continue if len ( val ) == 1 and suffixes . has_key ( val [ 0 ] ) : transition = ( x , suffixes [ val [ 0 ] ] ) transitions = states . get ( currentstate , [ ] ) if transition not in transitions : transitions . append ( transition ) states [ currentstate ] = transitions else : countstates += 1 transition = ( x , countstates ) transitions = states . get ( currentstate , [ ] ) if transition not in transitions : transitions . append ( transition ) states [ currentstate ] = transitions if finals in val : if countstates not in finalstates : finalstates . append ( countstates ) val . remove ( finals ) agenda . append ( ( countstates , val , tuple ( list ( history ) + [ currentstate ] ) ) ) merged = { } for key in statesuffixes . keys ( ) : val = tuple ( statesuffixes [ key ] ) del statesuffixes [ key ] if statesuffixes . has_key ( val ) : merged [ key ] = statesuffixes [ val ] else : statesuffixes [ max ( ( key , val ) ) ] = min ( ( key , val ) ) statesuffixes = None for i in states . keys ( ) : newval = [ ] oldval = states [ i ] if oldval == None : continue for j in oldval : if merged . has_key ( j [ 1 ] ) : newval . append ( ( j [ 0 ] , merged [ j [ 1 ] ] ) ) else : newval . append ( ( j [ 0 ] , j [ 1 ] ) ) states [ i ] = newval myFSA = FSA ( ) agenda = [ ] for i in states [ 1 ] : agenda . append ( i ) myFSA . add ( 1 , i [ 0 ] , i [ 1 ] , None , None ) while True : if not agenda : break inp , state = agenda . pop ( ) val = states [ state ] if val : for i in val : agenda . append ( i ) myFSA . add ( state , i [ 0 ] , i [ 1 ] , None , None ) states = None existingstates = myFSA . getStates ( ) for i in finalstates : if i in existingstates : myFSA . setFinal ( i ) myFSA . setFinal ( 0 ) myFSA . setStart ( 1 ) return myFSA
Returns a non-deterministic minimal automaton incrementally generated from a word list.
Returns a non - deterministic minimal automaton incrementally generated from a word list .
"""Returns a non-deterministic minimal automaton incrementally generated from a word list.""" # store all the states and as value tuples of production and goal state # key: state # value: [ (to-state, emission-symbol), ... ] # this number is the currently highest numbered state # list of final states # INIT: store all words as starting from startstate # suffixes is used as helping data structure to eliminate duplicates # tuple list: state, [suffix1, suffix2, ... ], history=(state1, state2, ...) # empty suffixes! # store all suffixes for a state # get suffixes, if exist: # link this to final state # generate suffix and store in suffix list # only if the current state is not a final one too # if there is one suffix and it is in suffixes # link it to the state this suffix starts from # make new transition # check for equal subpaths in the end # hash table with transition and target state as key # and starting state as value # the target state converted to final vs. non-final # merge the states # change the states that need to be merged # new FSA # eliminate unnecessary states by traversing # erase unnecessary data
wlist