How to implement nfa in python

#nfa simulation for (a|b)*abb
#state 4 is a trap state


import sys

def main():
    transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]]
    input = raw_input("enter the string: ")
    input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly
    for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity
        if input[index]=='a':
            input[index]='0' 
        else:
            input[index]='1'

    final = "3" #set of final states = {3}
    start = 0
    i=0  #counter to remember the number of symbols read

    trans(transition, input, final, start, i)
    print "rejected"



def trans(transition, input, final, state, i):
    for j in range (len(input)):
        for each in transition[state][int(input[j])]: #check for each possibility
            if each < 4:                              #move further only if you are at non-hypothetical state
                state = each
                if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states
                    print "accepted"
                    sys.exit()
                trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:]
        i = i+1 #increment the counter


main()

Source: stackoverflow.com

Similar codes

20 votes161 views5 answers
Remove first character from string python
Python
0 vote141 views1 answer
Import re def check_time(text): pattern = ___ result = re.search(pattern, text) return result != None print(check_time("12:45pm")) # True print(check_time("9:59 AM")) # True print(check_time("6:60am")) # False print(chec
Python
1 vote142 views1 answer
Python KeyError: 'kivy.garden.graph'
Python
0 vote143 views1 answer
How a 16 mp camera looks like
Python
27 votes149 views6 answers
Install pandas
Python
1 vote166 views2 answers
Python turn off garbage collection
Python
0 vote167 views1 answer
How to stop a program after 1 second in python
Python
0 vote434 views2 answers
Idwt pywt
Python
1 vote229 views6 answers
Python filter function
Python
0 vote400 views1 answer
Django on delete set default
Python Django