# python – How are finite automata implemented in code?

## python – How are finite automata implemented in code?

A straightforward way to represent a DFA is as a dictionary of dictionaries. For each state create a dictionary which is keyed by the letters of the alphabet and then a global dictionary which is keyed by the states. For example, the following DFA from the Wikipedia article on DFAs

can be represented by a dictionary like this:

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

To run a dfa against an input string drawn from the alphabet in question (after specifying the initial state and the set of accepting values) is straightforward:

```
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, step through the string character by character, and at each step simply look up the next state. When you are done stepping through the string you simply check if the final state is in the set of accepting states.

For example

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

For NFAs you could store sets of possible states rather than individual states in the transition dictionaries and use the `random`

module to pick the next state from the set of possible states.

Here I present a recursive solution for NFA. Consider the following nfa:

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

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

**Note:** State 4 is a hypothetical state. Once you go to that state, you cant move further. It is helpful when you cant read the input from the current state. You directly go to the state 4 and say input is not accepted for current progress(Check other possibilities by going back). e.g, if you are at `q1`

, and the current input symbol is `a`

, you go to state 4 and stop computing 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 cant 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 Run(strings ending with abb are accepted):**

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

#### python – How are finite automata implemented in code?

Here is my version of a dfa implementation if youre looking for a more object-oriented one. I was however ever so slightly inspired by John Colemans 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: %snTerminal node: %sn % (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
```