How are finite automata implemented in code?

Question

How does one implement a DFA or an NFA for that matter in Python code?

What are some good ways to do it in Python? Are they ever used in real world projects?

Answer 1

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.

Answer 2

Here is my version of a dfa implementation if you're looking for a more object-oriented one. I was however ever so 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