1.3.4. Automata in fsm-tools¶

fsm-tools implements the Chomsky hierarchy as a strict Python inheritance chain. Each class is a formal restriction of the one above it — it inherits the full structure of its parent and constrains it further, removing degrees of freedom rather than adding them.

Automaton                              (abstract base)
└── TuringMachine                      (Type 0 — recursively enumerable)
    └── LinearBoundedAutomaton         (Type 1 — context-sensitive)
        └── PushdownAutomaton          (Type 2 — context-free)
            └── FiniteStateAutomaton   (Type 3 — regular, planned v0.2.0)

This structure means that isinstance(pda, TuringMachine) is True — every pushdown automaton is also a (constrained) Turing machine in the type system.

1.3.4.1. TuringMachine — Type 0¶

A Turing Machine operates on an infinite one-dimensional tape. Its transition function maps a (state, symbol) pair to a (next_state, write_symbol, direction) triple. It is the most general computational model — equivalent to any algorithm.

Key properties:

Infinite bidirectional tape, extended dynamically with blank symbols.
Read/write head moves left or right.
Accepts when reaching the accepting state.

1.3.4.2. LinearBoundedAutomaton — Type 1¶

A Linear Bounded Automaton is a Turing Machine whose tape is bounded to a length proportional to the input. It recognises exactly the context-sensitive languages.

Restriction over TuringMachine:

Tape size bounded: limits enforced per dimension.
Head raises IndexError if it reaches a tape boundary.

1.3.4.3. PushdownAutomaton — Type 2¶

A Pushdown Automaton replaces the tape with a LIFO stack. Its transition function maps a (state, input_symbol, stack_top) triple to a (next_state, stack_ops) pair, where stack_ops is the list of symbols pushed after popping the stack top.

Restriction over LinearBoundedAutomaton:

No tape: memory is a stack (last-in, first-out).
Input is read sequentially — no random access, no backtracking.
Acceptance by empty stack (bottom marker convention).

Transition 5-tuple:

(state_from, input_symbol, stack_top, state_to, stack_ops)

Where stack_ops is a list of symbols pushed after popping stack_top:

[] — pure pop (no push).
["A"] — replace top with A.
["A", "B"] — pop, then push B, then A (A ends on top).

Note

Epsilon-transitions (input_symbol=None) are reserved and will be implemented in v0.3.0. Passing None raises NotImplementedError in v0.1.0.

1.3.4.4. FiniteStateAutomaton — Type 3¶

Note

FiniteStateAutomaton is planned for v0.2.0 and is not yet implemented.

A Finite State Automaton is a Pushdown Automaton with no stack: transitions depend only on the current state and the current input symbol. It recognises exactly the regular languages.

Restriction over PushdownAutomaton:

No stack: transition function is (state, symbol) → state.
Accepts when reaching a designated accepting state after consuming all input.