from numpy import array

"""
Explanation: Computing FSAs
(C) 2017-2019 by Damir Cavar
Version: 1.0, September 2019
License: Creative Commons Attribution-ShareAlike 4.0 International License (CA BY-SA 4.0)
Introduction
Consider the following automaton:
<img src="NDFSAMatrixOp.png" caption="Non-deterministic Finite State Automaton" style="width: 200px;"/>
We can represent it in terms of transition tables. We will use the Python numpy module for that.
End of explanation
"""


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

"""
Explanation: 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.
End of explanation
"""


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

"""
Explanation: The following transition matrix shows that for the transitions associated with "b".
End of explanation
"""


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

"""
Explanation: The following transition matrix shows this for the transitions associated with "c".
End of explanation
"""


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

"""
Explanation: We can define the start state using an init vector. This init vector indicates that the start state should be 0.
End of explanation
"""


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

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


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

"""
Explanation: 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.
End of explanation
"""


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

"""
Explanation: 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:
End of explanation
"""


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

"""
Explanation: Just to verify once more, let us consider the sequence "aabc":
End of explanation
"""


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] ), [])

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

accept("aac")

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]
])

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]

paths("aabc")

"""
Explanation: 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:
End of explanation
"""


