**(C) 2017-2019 by Damir Cavar**

**Version:** 1.0, September 2019

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

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

```
In [6]:
```init = array([
[1, 0, 0]
])

```
In [7]:
```final = array([
[0],
[0],
[1]
])

```
In [9]:
```init.dot(a).dot(c).dot(final)

```
Out[9]:
```

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]:
```

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]:
```

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.

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

```
Out[47]:
```

```
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]:
```

**(C) 2016-2019 by Damir Cavar <dcavar@iu.edu>**