Lire en français

fsm-tools

A formal Python library for modelling automata in the Chomsky hierarchy.

Overview

fsm-tools provides a rigorous implementation of the four automaton families defined by Chomsky's grammar and language hierarchy:

Each class is a formal restriction of the one above it — inheriting its structure and constraining it further. The hierarchy is implemented as a strict inheritance chain:

Automaton
└── TuringMachine               (Type 0)
    └── LinearBoundedAutomaton  (Type 1)
        └── PushdownAutomaton   (Type 2)
            └── FiniteStateAutomaton  (Type 3)

Installation

pip install fsm-tools

Quick start

Turing Machine (Type 0)

from fsm_tools import TuringMachine

tm = TuringMachine(
    name="BinaryIncrement",
    chomsky="Recursively Enumerable",
    axes=1,
    blank_symbol="_",
    movement={"R": [1], "L": [-1]},
    register="q0",
    accept="qAccept",
    reject="qReject",
)

Pushdown Automaton (Type 2)

Recognition of the context-free language L = { aⁿbⁿ | n ≥ 1 }:

from fsm_tools import PushdownAutomaton

pda = PushdownAutomaton(
    name="anbn",
    stack_alphabet={"A"},
    bottom_symbol="Z",
)
pda.add_terminals("a", "b")
pda.set_register("q0")
pda.add_non_terminals("q1", "q2")

pda.add_transition("q0", "a", "Z", "q0", ["A", "Z"])
pda.add_transition("q0", "a", "A", "q0", ["A", "A"])
pda.add_transition("q0", "b", "A", "q1", [])
pda.add_transition("q1", "b", "A", "q1", [])
pda.add_transition("q1", "b", "Z", "q2", [])

pda.validate(["a", "b"])        # True
pda.validate(["a", "a", "b"])   # False

Extended hierarchy (pedagogical)

extended.py provides pedagogical variants that lift specific formal restrictions without changing the class of languages recognised — a direct illustration of the Church-Turing thesis:

from fsm_tools import ExtendedPushdownAutomaton

# L = { aⁿbⁿ | n ≥ 0 } — the epsilon-transition covers n = 0, which the
# base PushdownAutomaton rejects unconditionally.
epda = ExtendedPushdownAutomaton(name="anbn-eps", stack_alphabet={"A"}, bottom_symbol="Z")
epda.add_terminals("a", "b")
epda.set_register("q0")
epda.add_non_terminals("q1", "q2")

epda.add_transition("q0", "a", "Z", "q0", ["A", "Z"])
epda.add_transition("q0", "a", "A", "q0", ["A", "A"])
epda.add_transition("q0", "b", "A", "q1", [])
epda.add_transition("q1", "b", "A", "q1", [])
epda.add_transition("q1", "b", "Z", "q2", [])
epda.add_transition("q0", None, "Z", "q2", ["Z"])   # epsilon: accept n = 0

epda.validate([])               # True
epda.validate(["a", "b"])       # True

Documentation

Full documentation is available at fsm-tools.readthedocs.io.

Links

• PyPI
• GitHub
• Issues
• Contributing
• Changelog

License

This project is licensed under the CeCILL-C license. The French version is the legally authoritative reference — see LICENSE.fr.