ssfsm is a constructive library implementing deterministic finite state machines. The fun thing is, that it has a stupidly simple API.

pip install ssfsm==0.6.0


ssfsm - Stupidly Simple Finite State Machines

ssfsm is a constructive library implementing finite state machines (currently only deterministic finite automaton - DFAs). The fun thing is, that it has a stupidly simple API.


pip install ssfsm


A full documentation is in the works and you can look at some examples in the tests-directory but here are a few ideas on how the library works:

Basic construction of DFAs

# A DFA that accepts b*a(ab)*
import ssfsm
A = ssfsm.DFA()
A.One['a'] = A.Two
A.One['b'] = A.One
A.Two['ab'] = A.Two # a and b transition
A.Two = True # Set state Two to accepting

The initial state needs to be set with A().reset(A.One). You can also create an initial state with the constructor like A = ssfsm.Machine('One').

States can be deleted with the del statement

A().states # frozenset({<ssfsm.DFA_State object>, <ssfsm.DFA_State object>})
del A.Two
A().states # frozenset({<ssfsm.DFA_State object>})

Their transitions (and the transitions leading to them) will be removed as well.


Transitions are executed by calling the machine with the transition.

A('a') # a-Transition
A('ab') # a-Transition followed by b-Transition

The current state after the last transition is returned. Because of the order of execution, Machine('a') is Machine().state is True (given the transition exists) while Machine().state is Machine('a') may not be.


When cast to boolean, we see whether the DFA is in an accepting state or not.

if A:
  # baab is an accepted word
  # it is not


Constructing DFAs, even with a nice syntax, can be tedious. So here is polyfill:

A = ssfsm.DFA()
A.One['a'] = A.Two
A().alphabet = 'ab'
A().polyfill() # all remaining transitions are filled, to stay in the same state

You also can call polyfill() with a parameter to set all remaining transitions to a specific state like A().polyfill(A.Two).

The A().alphabet is determined by all the transitions that are defined. If you've allready defined your whole alphabet via the transitions, this is not neccessary. But for polyfill-usage, you can set an alphabet. This also deletes transitions that are not part of the alphabet.

A = ssfsm.DFA()
A.One['c'] = A.Two
A.One.transitions # frozenset({'c'})
A().alphabet = 'ab'
A.One.transitions # frozenset()


If you've painstakenly created a DFA and want to use it but, after usage, want to return to a previous state, you can use the with statement.

A = ssfsm.DFA()
# create all states and transitions
with A as A_copy:
  A_copy('a') # a-transition only in A_copy

Both copies are not considered equal and have disjunct states.

A machine also supports the copy/deepcopy api, which is used for the with-statement.


You can add decorators to functions so that with each function call, a transition in the machine is executed.

A = ssfsm.DFA()
# create all states and transitions

@ssfsm.emmit(A, 'a')
def foo():

foo() # the same as A('a')

The transition happens before the function is called so that the function will observe the new state of the machine.

If you want the transition to happen after the actual function call and observe the previous state, you can use the decorator emmit_after. emmit_before is an alias for emmit.

Machine operations

~Machine returns a negated copy of the Machine. The current and initial state of the negated copy are the current and initial state of the original Machine.

MachineA - MachineB returns a DFA that has all the accepting words of A without those of B (difference). Both DFAs need to be deterministic. Both DFAs need to have the same alphabet.

MachineA & MachineB returns a DFA that has all the accepting words of A that are also accepting words of B (intersection). Both DFAs need to be deterministic. Both DFAs need to have the same alphabet.

MachineA | MachineB returns a DFA that has all the accepting words of A and all accepting words of B (union). Both DFAs need to be deterministic. Both DFAs need to have the same alphabet.

MachineA ^ MachineB returns a DFA that has all the accepting words of A and all accepting words of B that are not accepting words of A and B (symmetric difference). Both DFAs need to be deterministic. Both DFAs need to have the same alphabet.

For the operations -, &, | and ^, the resulting machine has (as its states) the cross-product of the states of the original DFAs. The machine is not minimized (so it may have redundant and unreachable states).

MachineA + MachineB returns a DFA that has the concatenation of the languages of A and B so that the language of A + B is every word accepted by A concatenated with every word accepted by B.

For the operation + the states of the resulting machine have as their names a tuple where the first part is a state from A and the second part is a frozenset of states from B (or an empty set).

Information about machines

len(Machine) returns the number of states in the machine

Machine().state is the current state. writable

Machine().initial_state is the initial state. writable

Machine().states is the set of states

Machine().transitions returns the set of transitions as a three-tuple of (from, transition, to) representing the state-transition function as a set.

Machine().alphabet is the set of transitions/the alphabet of the machine. writable

Machine().deterministic is True when the machine is deterministic so that for every transition in the alphabet, every state in the machine has that transition and an inital state is defined.

Machine().reachable_states is the set of states reachable from the initial state (the empty set, if no inital state is set)

Machine().accepting_states is the set of states that are accepting

Machine().infinite_language and Machine().finite_language whether the by the automaton described language is finite or infinite.

Machine().get_pumping_lemma() returns a triple u,v,w so that any u v* w is in the language of the automaton. This triple can be used to show, that the language is infinite, using the pumping lemma. If the language is finite, this method returns None.

Machine().language returns a generator of all words of the language (as tuples of increasing length). The language might be infinite. The words are yielded with increasing length. If the alphabet can be sorted, words of the same length will be yielded in lexicographical order.

Machine().regular_language returns True, if the language described by the DFA is a regular language.

Machine().remove_unreachable_states() removes all states of the machine that are not reachable from the initial state.

Machine().minimized is True if the machine is already minimized. This works by minimizing the DFA and comparing the number of states.

Machine().get_minimized() returns a minimized copy of the DFA. It has neither unreachable nor redundant states and has the same language and alphabet as the original machine. If the original machine was in a specific state when it was minimized, the minimized copy will be in the same (or its equivalent) state. The states of the minimized DFA either have the same name as the states of the original or a tuple of the names of all states that specific state represents (equivalence class).

Machine().dot is the string representing the machine as a dot-graph.

If you don't like the Machine()-syntax to access the DFA, you can use the alternate syntax Machine._.alphabet and so on.

Information about states is the name of the state.

state.parent is the DFA the state is in.

state.transitions is the set of transitions the state has.

state.following is the set of states directly reachable via the transitions (1 step)

state.reachable is the set of states reachable via the transitions (1 or more steps)

state.accepting whether the state is an accepting state. writable

a in state whether a is a transition of the state.

state1 > state2 whether state2 is directly reachable from state1 (equivalent to state2 in state1.transitions)

state1 >> state2 whether state2 is reachable from state1 (equivalent to state2 in state1.reachable)

Programmatic quirks and implementation details

States can be accessed via the dot-operator as Machine.State. If you want to access states programmatically or want different qualifiers as state-names, you can also access them via Machine[State]. Therefore if A is a Machine, A.One and A['One'] are equivalent. Whereas the state A[1] or A[('Foo', 'Bar')] can not be created or accessed via the dot-operator.

A state is created when it is first accessed. Therefore a plain statement can have observable side-effects.

A = ssfsm.DFA()
'foo' in A # False # plain expression with side-effects
'foo' in A # True

Using Machine.State = True to set a state to accepting is syntactic sugar and is not equal to f = Machine.State; f = True. If you want to do something like that, the syntax is f = Machine.State; f.accepting = True. The accepting-property can also be read.

States and transitions are kept in dictionaries, therefore a state-identifier as well as all transitions need to be hashable.

Transitions are checked for iterability and if they are iterable, they are iterated over and the transitions are applied/created in order. Therefore Machine.State[''] = Machine.OtherState will not create a transition, neither will Machine('') apply a transition.

Machine()(), is like an empty transition and therefore an alias to Machine().state or Machine(()) or Machine('')

Due to how the del statement works, del m.A is not equivalent to a = m.A; del a. The latter does only remove the reference a from the frame and not the A-state from the machine.

Unit tests

Just run nosetests from within the project directory. The test-coverage (nosetests --with-coverage --cover-erase) should be quite high.

Further Work

In the future I want to do:

  • more tests
  • nondeterministic FAs
  • a nice documentation
  • more decorators to control program flow
  • other finite state machines than DFAs


This library is licensed under GPL 2.0