How are state machines implemented in code?

Question

How to implement dfa or nfa in this case in Python code?

What are some good ways to do this in python? And are they ever used in real projects?

Answer 1

A direct way to represent DFA is through a dictionary of dictionaries. For each state, create a dictionary that is entered in the letters of the alphabet, and then a global dictionary that is entered in accordance with the states. For example, the next DFA from the Wikipedia article on DFA

can be represented by the following dictionary:

 dfa = {0:{'0':0, '1':1}, 1:{'0':2, '1':0}, 2:{'0':1, '1':2}} 

To "start" dfa against an input string taken from the alphabet in question (after indicating the initial state and a set of accepted values) is simple:

 def accepts(transitions,initial,accepting,s): state = initial for c in s: state = transitions[state][c] return state in accepting 

You start in the initial state, type a string character by character and at each step you simply look at the next state. When you finish going through the line, you just check to see if the final state is in the set of receiving states.

for example

 >>> accepts(dfa,0,{0},'1011101') True >>> accepts(dfa,0,{0},'10111011') False 

For the NFA, you can store sets of possible states, rather than separate states in transition dictionaries, and use the random module to select the next state from the set of possible states.

Answer 2

So here I present a recursive solution for NFA.

consider the following nfa:

transitions can be represented using a list of lists as follows:

transition = [[[0,1],[0]], [[4],[2]], [[4],[3]], [[4],[4]],[[4],[4]]]

Note: State 4 is a hypothetical state. When you go into this state, you cannot move on. This is useful if you cannot read input from the current state. You directly go to state 4 and say that the input is not accepted for the current progress (check other possibilities by returning). for example, if you are in q1 and the current input character is 'a' , you go to state 4 and continue to calculate further.

here is the python code:

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

sample output: (lines ending in abb are accepted)

 enter the string: abb accepted enter the string: aaaabbbb rejected 

......

Answer 3

You don't need a for over range (len (input)) loop if you use recursion. You complicate the code too much. Here is a simplified version

 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 trans(transition, input, final, start) print "rejected" def trans(transition, input, final, state): for each in transition[state][int(input[0])]: #check for each possibility if each < 4: #move further only if you are at non-hypothetical state state = each if len(input)==1: if (str(state) in final): #last symbol is read and current state lies in the set of final states print "accepted" sys.exit() else: continue trans(transition, input[1:], final, state) #input string for next transition is input[i+1:] main() 

Answer 4

Here is my version of the dfa implementation if you are looking for a more object oriented one. However, I was slightly inspired by John Coleman's answer.

 class Node: def __init__(self, val): self.val = val self.links = [] def add_link(self, link): self.links.append(link) def __str__(self): node = "(%s):\n" % self.val for link in self.links: node += "\t" + link + "\n" return node def __add__(self, other): return str(self) + other def __radd__(self, other): return other + str(self) def equals(self, node): ok = (self.val == node.val) if len(self.links) == len(node.links): for i in range(len(self.links)): ok = ok and (self.links[i] == node.links[i]) return ok else: return False class Link: def __init__(self, from_node, etiquette, to_node): self.from_node = from_node self.etiquette = etiquette self.to_node = to_node def __str__(self): return "(%s --%s--> %s)" % (self.from_node.val, self.etiquette, self.to_node.val) def __add__(self, other): return str(self) + other def __radd__(self, other): return other + str(self) def equals(self, link): return (self.from_node == link.from_node) and (self.etiquette == link.etiquette) and (self.to_node == link.to_node) class Automata: def __init__(self, initial_node, nodes, terminal_node): self.initial_node = initial_node self.nodes = nodes self.terminal_node = terminal_node def get_next_node(self, current_node, etiquette): for link in current_node.links: if link.etiquette == etiquette: return link.to_node return None def accepts(self, string): node = self.initial_node for character in string: node = self.get_next_node(node, character) return self.terminal_node.equals(node) def __str__(self): automata = "Initial node: %s\nTerminal node: %s\n" % (self.initial_node.val, self.terminal_node.val) for node in self.nodes: automata += node return automata def __add__(self, other): return str(self) + other def __radd__(self, other): return other + str(self) if __name__ == '__main__': pass s0 = Node("s0") s1 = Node("s1") s2 = Node("s2") s0_0_s0 = Link(s0, '0', s0) s0_1_s1 = Link(s0, '1', s1) s1_0_s2 = Link(s1, '0', s2) s1_1_s0 = Link(s1, '1', s0) s2_0_s1 = Link(s2, '0', s1) s2_1_s2 = Link(s2, '1', s2) s0.add_link(s0_0_s0) s0.add_link(s0_1_s1) s1.add_link(s1_0_s2) s1.add_link(s1_1_s0) s2.add_link(s2_0_s1) s2.add_link(s2_1_s2) a = Automata(s0, [s0, s1, s2], s0) print(a) print(a.accepts('1011101')) #True print(a.accepts('10111011')) #False 

Answer 5

I have implemented dfa that works for any of dfa. But this is not in an object oriented scheme.

 states=list(map(int,input("Enter States : ").split(" "))) symbols=list(input("Enter Symbols : ").split(" ")) initial_state=int(input("Enter initial state : ")) final_states=list(map(int,input("Enter final states : ").split(" "))) transitions=[] inlists=[] for i in range(len(symbols)): print("Enter transitions for symbol "+symbols[i]+" from all states :") for j in range(len(states)): inlists.append(int(input())) transitions.append(inlists) inlists=[] cur_state=initial_state while(1): cur_state=initial_state string=input("Enter string : ") if string=='#': break for symbol in string: print("["+str(cur_state)+"]"+"-"+symbol+"->",end="") cur_state=transitions[symbols.index(symbol)][cur_state] if cur_state in final_states: print("["+str(cur_state)+"]") print("String is accepted.") else: print("["+str(cur_state)+"]") print("String is not accepted.")