how to implement nfa in python 1

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()

Here is what the above code is Doing:
1. It takes the input string and parses it into a list of 0's and 1's.
2. It then calls the trans function which takes the transition table, input string, set of final states, start state and a counter as arguments.
3. The trans function then checks for each possibility in the transition table and calls itself recursively.
4. The counter is used to keep track of the number of symbols read.
5. The input string for the next transition is input[i+1:]
6. The function returns "accepted" if the last symbol is read and the current state lies in the set of final states.
7. If the function returns nothing, it means that the string is rejected.

Similar Posts