A library for manipulating finite state machines
Project description
FiniteStateMachines
This package provides three classes for different types of finite state machines.
FiniteStateMachine
, for classical finite state machines over an alphabet in which all letters are weighted equally;WeightedFiniteStateMachine
, for finite state machines over an alphabet in which each transition has a weight that is a polynomial in x;CombinatorialFSM
, for finite state machines with no alphabet at all, in which transitions between a pair of states are just recorded with a weight that is an expression in x and possibly other variables.
It can be installed via pip with the command pip install finite_state_machines
. Questions, comments, and improvements welcome!
FiniteStateMachine
This is a Python class to perform basic operations on finite state machines, including union, intersection, and minimization.
>>> from finite_state_machines import FiniteStateMachine as FSM
>>> M = FSM.fsm_for_words_avoiding("000", alphabet=["0","1"])
>>> M.enumeration(10)
[1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504]
>>> N = FSM.fsm_for_words_avoiding("101", alphabet=["0","1"])
>>> N.enumeration(10)
[1, 2, 4, 7, 12, 21, 37, 65, 114, 200, 351]
>>> M.intersection(N).words_generated(3)
{'001', '010', '011', '100', '110', '111'}
>>> M.intersection(N).enumeration(10)
[1, 2, 4, 6, 9, 13, 19, 28, 41, 60, 88]
>>> M.union(N).enumeration(10)
[1, 2, 4, 8, 16, 32, 62, 118, 222, 414, 767]
WeightedFiniteStateMachine
In a weighted finite state machine, each transition is labeled with a weight that is a polynomial in x. This class has methods to generate words of a certain size ("length" is no longer the correct metric) and to count words of a given size without generating them with a dynamic programming algorithm. Functions are provided to convert back and forth between weighted and nonweighted FSMs. Intersection and union of such machines are not precisely defined and thus not implemented, and there is currently no minimization function.
>>> import sympy
>>> x = sympy.Symbol('x')
>>> from finite_state_machines import WeightedFiniteStateMachine as WFSM
>>> M = WFSM({"a", "b"}, 2, 0, {1}, {(0,"a"):(0,x),(0,"b"):(1,x),(1,"a"):(0,x**2),(1,"b"):(1,x**2)})
>>> [M.words_generated(i) for i in range(5)]
[set(), {'b'}, {'ab'}, {'aab', 'bb'}, {'aaab', 'abb', 'bab'}]
>>> M.enumeration(10)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
CombinatorialFSM
A combinatorial finite state machine (CFSM) has no alphabet. There are states (which in this implementation must be hashable), a single start state, a set of accepting states, and transitions between pairs of states that are weighted with sympy expressions that involve a main variable (x be default) and possibly other variables.
Construction of a CFSM is a bit different from the previous two classes. After creating the class, you feed it transitions and weights. The weight is added to any existing weight between these two same states.
The class comes with a minimization function and a function to write the transition matrix and solving routine to a Maple file.
>>> import sympy
>>> x, y, C = sympy.symbols('x y C')
>>> from finite_state_machines import CombinatorialFSM
>>> M = CombinatorialFSM()
>>> M.add_transition(0, 1, x*y)
>>> M.add_transition(0, 1, x**2)
>>> M.add_transition(0, 2, x*y**2/C)
>>> M.add_transition(0, 3, x*y**2/C)
>>> M.add_transition(1, 0, x*(1+y/2))
>>> M.add_transition(2, 1, x**2)
>>> M.add_transition(3, 1, x**2)
>>> M.set_start(0)
>>> M.set_accepting({0, 1})
>>> M.enumeration(5)
[1,
y,
y**2/2 + y + 1,
y**3/2 + y**2 + y/2 + 1 + 2*y**2/C,
y**4/4 + y**3 + 2*y**2 + 2*y + y**3/C + 2*y**2/C,
y**5/4 + y**4 + 3*y**3/2 + 2*y**2 + 5*y/2 + 1 + 2*y**4/C + 4*y**3/C]
>>> len(M.states)
4
>>> minimized = M.minimize()
>>> len(minimized.states)
3
>>> minimized.enumeration(5)
[1,
y,
y**2/2 + y + 1,
y**3/2 + y**2 + y/2 + 1 + 2*y**2/C,
y**4/4 + y**3 + 2*y**2 + 2*y + y**3/C + 2*y**2/C,
y**5/4 + y**4 + 3*y**3/2 + 2*y**2 + 5*y/2 + 1 + 2*y**4/C + 4*y**3/C]
>>> with open('CFSM_example.txt', 'w') as f:
>>> minimized.write_to_maple_file(f)
The produced Maple file is:
start := 1:
accepting := [1, 2]:
M := Matrix(3,3, storage=sparse):
M[1,2] := x**2  x*y:
M[1,3] := 2*x*y**2/C:
M[2,1] := x*(y/2  1):
M[3,2] := x**2:
M[1,1] := 1 + M[1,1]:
M[2,2] := 1 + M[2,2]:
M[3,3] := 1 + M[3,3]:
V := Vector(LinearAlgebra[Dimensions](M)[1]):
for a in accepting do V[a] := 1: od:
infolevel[solve] := 5:
xvec := LinearAlgebra[LinearSolve](M, V):
f := xvec[1]:
If this code is useful to you in your work, please consider citing it.
Bibtex entry:
@misc{FiniteStateMachines,
author = {Jay Pantone},
howpublished = {\url{https://github.com/jaypantone/FiniteStateMachines}},
month = {September},
note = {DOI: \url{https://doi.org/10.5281/zenodo.4592555}},
title = {Finite{S}tate{M}achines},
year = {2021}
}
Biblatex entry:
@software{FiniteStateMachines,
author = {Jay Pantone},
date = {2021},
doi = {10.5281/zenodo.4592555},
month = {9},
title = {FiniteStateMachines},
url = {https://github.com/jaypantone/FiniteStateMachines}
}
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for finite_state_machines1.2.2.tar.gz
Algorithm  Hash digest  

SHA256  7959f8287a5b6049665a30cdf7fbcb1112b4097e166e939a080f124e1fda2a93 

MD5  796a09d2a49d9d2bfab88d0cc079e4ee 

BLAKE2b256  4c4c8780273a3f42f2b9fc0a3190bafc1b409a419d3aad91f9fa35c6d348856d 
Hashes for finite_state_machines1.2.2py3noneany.whl
Algorithm  Hash digest  

SHA256  bf00c028470699499ace8e5e8cdf8cc4f0e53e05a81e2ff0524aaa6d10b31ad2 

MD5  3015ce1fde8914ec45ccdfa9719d80f7 

BLAKE2b256  3c809e336c89c9b8728d3c68f7164da87a33ed1175c16880e17e1aeadf6444f1 