how to implement nfa in python

1#nfa simulation for (a|b)*abb
2#state 4 is a trap state
3
4
5import sys
6
7def main():
8    transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]]]
9    input = raw_input("enter the string: ")
10    input = list(input) #copy the input in list because python strings are immutable and thus can't be changed directly
11    for index in range(len(input)): #parse the string of a,b in 0,1 for simplicity
12        if input[index]=='a':
13            input[index]='0' 
14        else:
15            input[index]='1'
16
17    final = "3" #set of final states = {3}
18    start = 0
19    i=0  #counter to remember the number of symbols read
20
21    trans(transition, input, final, start, i)
22    print "rejected"
23
24
25
26def trans(transition, input, final, state, i):
27    for j in range (len(input)):
28        for each in transition[state][int(input[j])]: #check for each possibility
29            if each < 4:                              #move further only if you are at non-hypothetical state
30                state = each
31                if j == len(input)-1 and (str(state) in final): #last symbol is read and current state lies in the set of final states
32                    print "accepted"
33                    sys.exit()
34                trans(transition, input[i+1:], final, state, i) #input string for next transition is input[i+1:]
35        i = i+1 #increment the counter
36
37
38main()
39