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?

Complice

This question is super broad. It is likely to be closed unless you can narrow it to a specific objectively answerable question. Anyway... Yes, they are used in real world projects. A "state machine" is a common implementation technique. Here's one possible approach in python: python-3-patterns-idioms-test.readthedocs.org/en/latest/… – Lymanlymann

True regular expressions can be matched by DFAs; in fact, any regular language can be represented as either a regular expression or a DFA. – Bloodline

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.

Noe

Answer 2

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 can't move further. It is helpful when you can't 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 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 Run(strings ending with abb are accepted):

enter the string: abb
accepted

enter the string: aaaabbbb
rejected

Sanasanabria

Answer 3

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

Gaulin

Answer 4

You don't need a for loop over range(len(input)) if you're using recursion. You're overcomplicating the code. Here's 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()

Strappado

Answer 5

I have implemented dfa which works for any of the dfa. But this is not in object oriented pattern.

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.")

Levison

Answer 6

Accepting string 101* and 001* modification of @John Coleman

#Dfa for accepting only 101+00101001

dfa101 = {0:{'1':1},
       1:{'0':2},
       2:{'1':3},
       3:{'0':3, '1':3}}

#Dfa for accepting only 001+00101001
dfa001={0:{'0':1},
       1:{'0':2},
       2:{'1':3},
       3:{'0':3, '1':3}}



def accepts(transitions,initial,accepting,s):
    state = initial
    try:
        for c in s:
            state = transitions[state][c]
        if(state in accepting):
            return 'Accepted'
        else:
            return 'Rejected'
    except:
        return 'Rejected'
print('Dfa of 101+ ',accepts(dfa101,0,{3},'10101111000')) #Accepted

print('Dfa of 001+ ',accepts(dfa001,0,{3},'00101010101')) #Accepted

Appressed

Answer 7

To showcase my solution, let's take the following DFA as an example:

Language over 𝛴 = (0, 1) containing strings that are either made up of only 1’s or strings in which every 0 is followed by a 1.

The transition table for this DFA is:

delta	0	1
->*S	A	S
A	D	S
D	D	D

My program, written in Python3, is designed to accept the transition table of any DFA over the alphabet (0, 1) to check whether a string will be accepted by the DFA or not.

To use my program, we have to input the above transition table in the following format into a text file named fa.txt present in the same directory as the program.

fa.txt:

->*s(a,s)
a(d,s)
d(d,d)

For start state, the state name must be preceded by -> and a final state must be preceded by *. In case the start state is a final state, -> must come before *. The state name must be only one character in length. The start state must be named s. The order of the states in the TXT file is irrelevant.

The code:

file = open("fa.txt", "r")
l = file.readlines()
x = 0

def findState(state):
    lines = l
    for i in range(0, len(lines)):
        if lines[i][0] == '-':
            lines[i] = lines[i][2::]
        if lines[i][0] == '*':
            if state == lines[i][1]:
                return [lines[i][3], lines[i][5], 1]
        if lines[i][0] == state:
            return [lines[i][2], lines[i][4], 0] # state to go to on 0, state to go to on 1, is it final?

s = input("Enter a binary string to test it against the DFA in file fa.txt: ")
on0_on1 = findState('s') # start state
print("s", end = "")

for c in range(0, len(s)):
    if s[c] != '0' and s[c] != '1':
        print("Fail")
        exit(0)
    if s[c] == '0':
        print(' ---0--->', on0_on1[0], end = '')
        on0_on1 = findState(on0_on1[0])
    else:
        print(' ---1--->', on0_on1[1], end = '')
        on0_on1 = findState(on0_on1[1])
    if on0_on1[2] == 1 and c == len(s) - 1:
        print("\nPass")
    elif c == len(s) - 1 and on0_on1[2] == 0:
        print("\nFail")

Daukas