Automatas

[thorwhalen]

Finite automatas and regular expressions are equivalent from an expressivity point of view. In fact, it's more or less what a programming language does with a regular expression to "use" it: It transforms it into a finite automata.

A finite automata 's raison d'être is to just decide if a string of symbols "is" or "is not" (in da club): It does so by reading the string of symbols, which trigger state changes (via a "transition matrix"): The string is "accepted" if the state the automata is in after reading the whole string is an "accept state".

But here, we're more interested in

• the sequence of states themselves; a practical way to generate a stream from another one
• the state control mechanism, which can be used to carry out control-flow logic

[thorwhalen]

A finite automata has a finite set of states and "alphabet" of symbols it reads. Here we'll define something simpler, yet much more general.

Instead of having to define a set of states and alphabet of "symbols", we'll just, by default, allow any of these.
Since we're more interested in the sequence of states made by reading the stream of symbols, we don't need the definition of any "accept state" either. So all we're left with, from the format definition of a finite automata is the need for a "transition function" and an "initial state".

This leads us to an automata that is simpler, but more general.

(Note that it's open-closed though: If we want to add constraints to make it a actual finite automata, we can do this by extending the basic automata below.)

TDD

from typing import Any, TypeVar, Mapping, Iterable, Callable, Tuple

State = TypeVar('State')
Symbol = TypeVar('Symbol')
Automata = Callable[[State, Iterable[Symbol]], Iterable[State]]

TransitionFunc = Callable[[State, Symbol], State]
AutomataFactory = Callable[[TransitionFunc], Automata]


def test_automata(automata):
    # A automata that even number of 0s and 1s
    transition_func = mapping_to_transition_func(
        {
            ('even', 0): 'odd',
            ('odd', 1): 'even',
        },
        strict=False  # so that all (state, symbol) combinations not listed have no effect
    )
    fa = automata(transition_func)
    symbols = [0, 1, 0, 1, 1]
    it = fa('even', symbols)
    next(it) == 'even'  # reads 0, stays on state 'even'
    next(it) == 'odd'   # reads 1, applies the ('even', 0): 'odd' transition rule
    next(it) == 'odd'   # reads 0, stays on state 'odd'
    next(it) == 'even'  # reads 1, applies the ('odd', 1): 'even' transition rule
    next(it) == 'odd'   # reads 1, applies the ('even', 0): 'odd' transition rule

    # We can feed the automata with any iterable, and gather the "trace" of all the states 
    # it went through like follows. Notice that we can really put any symbol in the 
    # iterable, not just 0s and 1s. The automata will just ignore the symbols (remainingin 
    # in the same state) if there is no transition for the current state and the symbol.
    assert list(fa('even', [0, 1, 0, 42, 'not_even_a_number', 1])) == [
        'odd', 'even', 'odd', 'odd', 'odd', 'even'
    ]


    # When the automata only works on a finite set of states and symbols, we call it 
    # a "finite automata". Above, we could have specified strict=True and explicitly 
    # list all possible combinations in the transition mapping to get a finite automata.
    # Here's an example where neither states nor symbols have to be from a finite set
    def my_special_transition(state: State, symbol: Symbol) -> State:
        if state in symbol or symbol in state:
            # if the symbol is part of, or contains the state, we return the symbol
            return symbol
        else:  # if not we remain in the same state
            return state
        

    fa = automata(my_special_transition)
    symbols = [
        'a', 'b', 'c', 'ab', 'abc', 'abdc', 'abcd'
    ]
    assert list(fa('a', symbols)) == [
        'a', 'a', 'a', 'ab', 'abc', 'abc', 'abcd'
    ]


def mapping_to_transition_func(
        mapping: Mapping[Tuple[State, Symbol], State], 
        strict: bool = True
) -> TransitionFunc:
    """
    Helper to make a transition function from a mapping of (state, symbol)->state.
    """
    if strict:
        def transition_func(state: State, symbol: Symbol) -> State:
            return mapping[(state, symbol)]
    else:
        def transition_func(state: State, symbol: Symbol) -> State:
            return mapping.get((state, symbol), state)
    return transition_func

[thorwhalen]

Functional implementation

# functional version
def _basic_automata(
        transition_func: TransitionFunc, 
        initial_state: State, 
        symbols: Iterable[Symbol]
) -> State:
    state = initial_state
    for symbol in symbols:
        # Note: if the (state, symbol) combination is not in the transitions
        #     mapping, the state is left unchanged.
        state = transition_func(state, symbol)
        yield state

from functools import partial

automata: AutomataFactory = (
    lambda transition_func: partial(_basic_automata, transition_func)
)
# # NerdNote: Could do it like this too
# basic_automata: AutomataFactory = partial(partial, _basic_automata)

test_automata(automata)

[thorwhalen]

Class implementation

from dataclasses import dataclass

@dataclass
class BasicAutomata:
    transition_func: TransitionFunc
    _current_state: State = None

    def __call__(self, state: State, symbols: Iterable[Symbol]) -> State:
        self._current_state = state
        for symbol in symbols:
            yield self.transition(symbol)
   
    def transition(self, symbol: Symbol) -> State:
        self._current_state = self.transition_func(self._current_state, symbol)
        return self._current_state
    
test_automata(BasicAutomata)

[thorwhalen]

This graph shows each possible transition (that is, for every combination of the four states and two symbols, we explicitly point to the resulting state):

But, you can also take the convention that any arrow that is missing (that is, any state for which you didn't specify what to do with some symbol) should be understood to mean "no change", that is, that you should remain in the same state, unless you see one of the listed symbols. This helps to lighten the graph a bit, making it more readable:

[thorwhalen]

Here's a flow (with a decision node) that uses this state machine.
The use case is that of the "Turning a recording on and off" section of the meshed "flow-control" notebook (similar to the base problem of Multi-channel based segmenter).

Note though, that the semantics of the diagram below are not well defined (or defined at all!). Really, (1) the open state should trigger the creation of a sequence and then append the chk to it and (2) the close state should first append the chk, and then close the sequence. This desire is not specified on the graph at all.