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