Computing FSAs

Version: 1.0, September 2019

License: Creative Commons Attribution-ShareAlike 4.0 International License (CA BY-SA 4.0)

Introduction

Consider the following automaton:

We can represent it in terms of transition tables. We will use the Python numpy module for that.



In [1]:

    
from numpy import array

The transitions are coded in terms of state to state transitions. The columns and rows represent the states 0, 1, and 2. The following transition matrix shows all transitions that are associated with the label "a", that is from 0 to 0, from 0 to 1, and from 1 to 0.



In [3]:

    
a = array([
    [1, 1, 0],
    [1, 0, 0],
    [0, 0, 0]
])

The following transition matrix shows that for the transitions associated with "b".



In [4]:

    
b = array([
    [0, 1, 0],
    [0, 1, 0],
    [0, 0, 0]
])

The following transition matrix shows this for the transitions associated with "c".



In [5]:

    
c = array([
    [0, 0, 0],
    [0, 0, 1],
    [0, 0, 0]
])

We can define the start state using an init vector. This init vector indicates that the start state should be 0.



In [6]:

    
init = array([
    [1, 0, 0]
])

The set of final states can be encoded as a column vector that in this case defines state 3 as the only final state.



In [7]:

    
final = array([
    [0],
    [0],
    [1]
])

If we want to compute the possibility for a sequence like "aa" to be accepted by this automaton, we could compute the dot product of the init-vector and the a matrices, with the dot product of the final state.



In [9]:

    
init.dot(a).dot(c).dot(final)









    Out[9]:





array([[1]])

The 0 indicates that there is no path from the initial state to the final state based on a sequence "aa".

Let us verify this for a sequence "bc", for which we know that there is such a path:



In [8]:

    
init.dot(b).dot(c).dot(final)









    Out[8]:





array([[1]])

Just to verify once more, let us consider the sequence "aabc":



In [10]:

    
init.dot(a).dot(a).dot(b).dot(c).dot(final)









    Out[10]:





array([[3]])

There are obviously three paths in our Non-deterministic Finite State Automaton that generate the sequence "aabc".

Wrapping the Process into a Function

We could define the FSA above as a 5-tuple $(\Sigma, Q, i, F, E)$, with:

$\Sigma = \{a, b, c\}$, the set of symbols.

$Q = \{ 0, 1, 2 \}$, the set of states.

$i \in Q$, with $i = 0$, the initial state.

$F \subseteq Q$, with $F = \{ 2 \}$, the set of final states.

$E \subseteq Q \times (\Sigma \cup \epsilon) \times Q$, the set of transitions.

$E$ is the subset of tuples determined by the cartesian product of the set of states, the set of symbols including the empty set, and the set of states. This tuple defines a transition from one state to another state with a specific symbol.

$E$ could also be defined in terms of a function $\delta(\sigma, q)$, with $\sigma$ an input symbol and $q$ the current state. $\delta(\sigma, q)$ returns the new state of the transition, or a failure. The possible transitions for any given symbol from any state can be defined in a transition table:

	a	b	c
0	0, 1	1	-
1	0	1	2
2:	-	-	-

We can define the automaton in Python:



In [45]:

    
S = set( ['a', 'b', 'c'] )
Q = set( [0, 1, 2] )
i = 0
F = set( [ 2 ] )
td = { (0, 'a'): [0, 1],
       (1, 'a'): [0],
       (0, 'b'): [1],
       (1, 'b'): [1],
       (1, 'c'): [2]
     }

def df(state, symbol):
    print(state, symbol)
    return td.get(tuple( [state, symbol] ), [])



In [46]:

    
def accept(sequence):
    agenda = []
    state = i
    count = len(sequence)
    agenda.append((state, 0))
    while agenda:
        print(agenda)
        if not agenda:
            break
        state, pos = agenda.pop()
        states = df(state, sequence[pos])
        if not states:
            print("No transition")
            return False
        state = states[0]
        if pos == count - 1:
            print("Reached end")
            if F.intersection(set(states)):
                return True
            break
        for s in states[1:]:
            agenda.append( (s, pos+1) )
    if state in F:
        print("Not final state")
        return True
    return False



In [47]:

    
accept("aac")









    



[(0, 0)]
0 a
[(1, 1)]
1 a






    Out[47]:





False



In [14]:

    
alphabetMatrices = {}
alphabetMatrices["a"] = array([
    [1, 1, 0],
    [1, 0, 0],
    [0, 0, 0]
])
alphabetMatrices["b"] = array([
    [0, 1, 0],
    [0, 1, 0],
    [0, 0, 0]
])
alphabetMatrices["c"] = array([
    [0, 0, 0],
    [0, 0, 1],
    [0, 0, 0]
])
alphabetMatrices["default"] = array([
    [0, 0, 0],
    [0, 0, 0],
    [0, 0, 0]
])



In [17]:

    
def paths(seq):
    res = init
    for x in seq:
        res = res.dot( alphabetMatrices.get(x, alphabetMatrices["default"]) )
    return res.dot(array([
    [0],
    [0],
    [1]
]))[0][0]



In [18]:

    
paths("aabc")









    Out[18]:





3