Advanced Automata¶

This page documents the formal Chomsky hierarchy classes defined in fsm_tools.advanced. All classes are exported from the top-level fsm_tools package.

Grammar¶

class fsm_tools.Grammar(automaton: Automaton | None = None)[source]

Bases: object

Represents a formal grammar and provides a structure for defining the components and rules used for language generation or recognition.

The grammar consists of the following key components:

alphabet

The set of terminal symbols (the alphabet) used in the grammar.

Type:: set

states

The set of non-terminal symbols that define the recursive structure of the grammar.

Type:: set

rules

A list of production rules, possibly nested, that define the transformations between non-terminals and terminals.

Type:: list

start

The start symbol of the grammar, that should be non-terminals component.

Type:: any

automaton

The automaton that processes the grammar and validates or generates strings.

Type:: Automaton

Initializes the Grammar class with the components necessary for language recognition or generation.

Parameters:: automaton (Automaton) – The automaton that processes the grammar and validates or generates strings.

get_type() → int[source]

Returns the type of the automaton (e.g., finite state automaton, Turing machine, etc.).

Returns:: The type of the grammar (type 0, 1, 2, 3)
Return type:: int

reset_alphabet()[source]

Resets the alphabet (terminal symbols) of the grammar to an empty set.

This method is useful when the alphabet needs to be redefined from scratch.

reset_states()[source]

Resets the states (non-terminal symbols) of the grammar to an empty set.

This method is useful when the set of states needs to be redefined from scratch.

reset_rules()[source]

Resets the list of production rules to an empty list.

This method is useful when the set of rules needs to be redefined from scratch.

reset()[source]

Resets all components of the grammar: alphabet, states, and rules.

This method provides a full reset of the grammar, clearing all components and allowing for a fresh definition of the grammar.

Automaton¶

class fsm_tools.Automaton(name: str = '', *, chomsky: str)[source]

Bases: object

Represents the base class for automata, providing a structure for automata that process formal grammars. This class serves as the foundation for specific types of automata, such as DFA, PDA, LBA, or TM, that can be used to recognize or generate strings based on the rules of a given grammar.

GRAMMAR

Reference to Chomsky grammar hierarchy (e.g., “Regular”, “Context-Free”).

Type:: str

TYPE

Reference to Chomsky grammar hierarchy type, which corresponds to the automaton’s type.

Type:: int

name

The name of the automaton. This can be used to identify different types of automata.

Type:: str

grammar

An empty Grammar object initialized as part of the automaton. The grammar can be populated later with terminals, non-terminals, and rules.

Type:: Grammar

Initializes the Automaton with a given name and a given Grammar classification name.

Parameters:

name (str) – The name of the automaton, which can be used to identify the automaton.
chomsky (str) – The Chomsky grammar classification type to be used, which defines the automaton’s behavior.

Raises:

KeyError – If the given Chomsky grammar type is not recognized.

GRAMMAR: str = ''

TYPE: int = 99

change_classification(classification: str)[source]

get_terminals()[source]

Returns the set of terminal symbols (alphabet) used in the grammar.

Returns:: A set of terminal symbols.
Return type:: set
Raises:: ReadError – If no terminals have been defined in the grammar.

add_terminals(*terminals: any)[source]

Adds terminal symbols to the grammar’s alphabet.

Parameters:: terminals – One or more terminal symbols to be added.
Raises:: AddError – If a symbol is already in the alphabet or states.

remove_terminals(*terminals: any)[source]

Removes terminal symbols from the grammar’s alphabet.

Parameters:: terminals – One or more terminal symbols to be removed.
Raises:: RemoveError – If a symbol is not found in the alphabet.

modify_terminal(existing_terminal: any, new_terminal: any)[source]

Modifies an existing terminal symbol by removing it and adding a new one.

Parameters:

existing_terminal – The terminal symbol to be replaced.
new_terminal – The new terminal symbol to add.

Raises:

AddError – If the new terminal is already present in the alphabet.
ModifyError – If the existing terminal cannot be modified due to errors.

withdraw_terminal()[source]

Clears all terminal symbols (alphabet) from the grammar.

Raises:: ReadError – If the alphabet is empty when trying to withdraw terminals.

get_states()[source]

Returns the set of non-terminal symbols (states) used in the grammar.

Returns:: A set of non-terminal symbols (states).
Return type:: set
Raises:: ReadError – If no states have been defined in the grammar.

add_non_terminals(*non_terminals: any)[source]

Adds non-terminal symbols to the grammar’s set of states.

Parameters:: non_terminals – One or more non-terminal symbols to be added.
Raises:: AddError – If a symbol is already in the states.

remove_non_terminals(*non_terminals: any)[source]

Removes non-terminal symbols from the grammar’s set of states.

Parameters:: non_terminals – One or more non-terminal symbols to be removed.
Raises:: RemoveError – If a symbol is not found in the states.

modify_non_terminal(existing_non_terminal: any, new_non_terminal: any)[source]

Modifies an existing non-terminal symbol by removing it and adding a new one.

Parameters:

existing_non_terminal – The non-terminal symbol to be replaced.
new_non_terminal – The new non-terminal symbol to add.

Raises:

AddError – If the new non-terminal is already present in the states.
ModifyError – If the existing non-terminal cannot be modified due to errors.

withdraw_non_terminal()[source]

Clears all non-terminal symbols (states) from the grammar.

Raises:: ReadError – If the states are empty when trying to withdraw non-terminals.

get_rules()[source]

Returns the list of production rules used in the grammar.

Returns:: A list of production rules.
Return type:: list
Raises:: ReadError – If no rules have been defined in the grammar.

add_rules(*rules: any)[source]

Adds production rules to the grammar.

Parameters:: rules – One or more production rules to be added.

remove_rules(*rules: any)[source]

Removes production rules from the grammar.

Parameters:: rules – One or more production rules to be removed.
Raises:: RemoveError – If a rule is not found in the grammar’s list of rules.

withdraw_rules()[source]

Clears all production rules from the grammar.

Raises:: RemoveComponentError – If the rules are empty when trying to withdraw rules.

withdraw_grammar()[source]

Clears all components of the grammar (alphabet, states, rules).

This method provides a full reset of the grammar, clearing all its components.

TuringMachine¶

class fsm_tools.TuringMachine(name: str, axes: int = 1, blank_symbol: str = '_', movement: dict | None = None, register: str = '', accept: str = 'OK', reject: str = 'nOK', chomsky: str = 'Recursively Enumerable')[source]

Bases: Automaton

Represents a Turing Machine (TM), a type of automaton capable of simulating any algorithm. It extends the base Automaton class to incorporate specific attributes and operations needed for Turing Machine computation. The machine operates on a tape and has the ability to read, write, and move the head along the tape based on predefined rules.

This Turing Machine is specifically associated with the processing of Type 0 languages, which are also known as recursively enumerable languages. Type 0 languages represent the most general class of languages in the Chomsky hierarchy, which includes all languages that can be recognized by a Turing Machine. These languages are not necessarily decidable, but they can be enumerated by a machine that may not halt for all inputs.

tape

The tape (or tape array) that the Turing Machine operates on. Each cell in the tape contains a symbol from the alphabet. The tape is considered infinite in both directions, and its cells are initially filled with the blank symbol.

Type:: list

head

The position of the read/write head on the tape. The head moves left or right based on the machine’s transition rules.

Type:: int

register

The current state of the Turing Machine. This is used to determine the next action based on the current state and the symbol under the head.

Type:: str

blank

The blank symbol, representing an empty or uninitialized tape cell.

Type:: str

moves

Defines movements allowed to the Turing Machine. Default moves allowed are forward (F) and backward (B). Turing Machines may have more than 2 movements.

Type:: str

validation

A dictionary that stores the accept and reject states of the Turing Machine. The machine halts when it enters the accept or reject state.

Type:: dict

step(self)[source]: Executes one step of the Turing Machine based on the current state and the symbol under the head. The machine transitions to a new state, writes a symbol, and moves the head. The transition is determined by the current state and symbol, based on the rules defined in self.grammar.rules.

get_rules(self): Returns the list of current rules or transition actions. These rules are associated with the grammar of the Turing Machine.

Associations:

The self.grammar.rules attribute will contain the set of transition rules for the Turing Machine. Each rule is typically represented as a tuple or structured action that includes: - The current state (state_from) - The current symbol being read (symbol) - The next state to transition to (state_to) - The symbol to write on the tape (write_symbol) - The direction to move the head (L or R for left or right).
self.grammar.alphabet: The alphabet of the Turing Machine includes both the symbols that the machine can read from and write to the tape, as well as the blank symbol. Each symbol in the tape should belong to this alphabet.
self.grammar.states: The set of states includes the machine’s current state and any states involved in transitions. The accept and reject states are also included, and the machine halts when it reaches one of these states.
self.grammar.rules: A list of rules that define the machine’s behavior. Each rule maps a pair of current state and symbol to a next state, symbol to write, and head movement direction.

Additional Parameters:

The blank symbol (blank) is used to represent an empty tape cell. This is an important concept for Turing Machines, as it defines the boundary of the non-empty portion of the tape. The blank symbol is added to the alphabet and used throughout the computation.
state: The dictionary that holds the names of the accept and reject states. These are crucial for halting the machine when the computation is finished or when the input is rejected.

Notes

Turing Machines are associated with Type 0 languages (recursively enumerable languages) in the Chomsky hierarchy, which are the most general class of formal languages. Type 0 languages include all languages that can be recognized by a Turing Machine, regardless of whether they are decidable or not.
A Turing Machine can perform unbounded computations on an infinite tape, making it capable of recognizing languages that are undecidable but still recursively enumerable.
The transition rules (self.grammar.rules) are crucial to the functionality of the machine, as they define how the machine progresses through its states based on the current symbol on the tape.
The machine halts when it enters either the accept or reject state, signifying that the computation is complete or that the input is rejected.

Initializes the Turing Machine with a given name and the blank symbol (defaults to “_”). Inherits from the base Automaton class and initializes the tape, head, index, and register. Also, the blank symbol is set, and accept/reject states are added to the machine.

Parameters:

name (str) – The name of the machine to be initialized.
axes (int) – The axes of the machine to be initialized.
blank_symbol (str | "_") – The blank symbol, representing an empty or uninitialized tape cell.
movement (dict) – dictionary of movement
register (str | "") – The current state of the Turing Machine. This is used to determine the next action based on the current state and the symbol under the head.
accept (str | "OK") – The accept state to be initialized.
reject (str | "nOK") – The reject state to be initialized.

set_tape(content: List[Any], location: List[int] | None = None) → None[source]

Initializes the tape with a list of symbols and places the head at the starting index. Ensures that the head position does not exceed the limits of the tape and verifies that the content is valid based on the machine’s alphabet.

Parameters:

content (List[Any]) – The list of symbols to place on the tape. This list must be a nested list structure matching the dimensions of the tape.
location (List[int] | None) – The starting position of the head on the tape. Should be a list with the same number of dimensions as self.axes. Defaults to the origin of the tape.

Returns:

None

Return type:

None :raise ReadError: If any symbol in the tape_content is not part of the alphabet.

set_register(register: str) → None[source]

Initializes the register with a list of symbols and places the head at the starting index.

Parameters:: register (str) – The list of symbols to place in the tape.
Returns:: None
Return type:: None

set_moves(**moves) → None[source]

Initializes the moves with a list of symbols and places the head at the starting index.

Parameters:: moves (list of str) – The list of symbols to place in the tape.
Returns:: None
Return type:: None

read() → Any[source]: Read the symbol at the current position of the head.

write(symbol: any) → None[source]

Writes a symbol at the current head position on the multidimensional tape. The symbol is written based on the head’s position across all dimensions. If the symbol is not part of the alphabet, it is added automatically.

Parameters:: symbol (any) – The symbol to write at the current head position.

move(direction: str) → None[source]

Moves the head of the Turing Machine in the specified direction.

Parameters:: direction (str) – The direction to move the head of the Turing Machine
Returns:: None
Return type:: None

add_transition(state_from: str, symbol: any, state_to: str, write_symbol: any, move_direction)[source]

Adds a transition rule to the Turing Machine’s transition table. This rule defines what the Turing Machine should do when it encounters a specific symbol in a given state.

A transition for a Turing Machine includes the following components:

The current state (state_from): The state the machine is in before performing the action.
The current symbol (symbol): The symbol that is under the machine’s read/write head (can be of any type).
The next state (state_to): The state the machine should transition to.
The symbol to write (write_symbol): The symbol to be written on the tape (can be of any type).
The direction to move (move_direction): The direction in which the head should move after writing the symbol (‘L’ for left, ‘R’ for right).

These components align with the formal components of a Type-0 grammar (recursively enumerable grammar):

The states of the machine correspond to the non-terminals in the grammar.
The symbols under the head correspond to the terminals in the grammar.
The transition rules themselves can be considered as production rules in the grammar that specify how non-terminals (states) interact with terminals (symbols).

This method adds the transition to the Turing Machine’s internal transition table, which is stored in self.grammar.rules. The rules can be seen as a form of production that modifies the state and the tape contents.

Parameters:

state_from (str) – The current state of the machine.
symbol (any) – The symbol under the head of the machine.
state_to (str) – The current state of the machine.
write_symbol (any) – The symbol to write on the tape.
move_direction (str) – The direction to move the head, should be one of the valid directions in self.move.

Returns:

None

Return type:

None

Raises:

ReadError – If the symbol is not in the alphabet of the Turing Machine.
ValueError – If the symbol is not in the alphabet of the Turing Machine.

step()[source]: Execute one step of the Turing Machine based on current state and symbol.

LinearBoundedAutomaton¶

class fsm_tools.LinearBoundedAutomaton(name: str, tape_size: List[int], axes: int = 1, blank_symbol: str = '_', movement: dict | None = None, register: str = '', accept: str = 'OK', reject: str = 'nOK')[source]

Bases: TuringMachine

Represents a Linear Bounded Automaton (LBA), a type of automaton that simulates a Turing Machine but with a tape limited to the size of the input across multiple dimensions. This model can recognize context-sensitive languages (Type 1 in the Chomsky hierarchy).

tape

The multidimensional tape (or array) on which the automaton operates.

Type:: list

head

The position of the read/write head in the tape for each dimension.

Type:: list

register

The current state of the automaton.

Type:: str

blank

The blank symbol representing an empty tape cell.

Type:: str

limits

The list of size limits for each dimension of the tape.

Type:: list

validation

A dictionary containing the accept and reject states.

Type:: dict

step(self)[source]: Executes one step of the automaton based on the current state and the symbol under the head.

get_rules(self): Returns the list of current rules of the automaton.

extend_tape(self): Dynamically extends the tape within the dimensional limits.

Initializes the Linear Bounded Automaton with a given name, dimensional limits, and blank symbol.

Parameters:

name (str) – The name of the automaton.
tape_size (list) – A list of size limits for each dimension of the tape.
blank_symbol (str) – The blank symbol representing an empty tape cell.
movement (dict) – A dictionary of allowed movements.
register (str) – The current state of the automaton.
accept (str) – The accept state.
reject (str) – The reject state.

set_tape(content: List[any], location: List[int] | None = None) → None[source]

Initializes the tape with a multidimensional array of symbols and places the head at the starting position. The tape size will not exceed the defined limits.

Parameters:

content (list) – List of symbols to place on the tape.
location (list) – Starting position of the head.

Raises:

ValueError – If the content length exceeds the tape limit.

step()[source]: Executes one step of the automaton based on the current state and the symbol under the head.

PushdownAutomaton¶

class fsm_tools.PushdownAutomaton(name: str, stack_alphabet: set | None = None, bottom_symbol: str = 'Z', accept: str = 'OK', reject: str = 'nOK')[source]

Bases: LinearBoundedAutomaton

A Pushdown Automaton (PDA) — Type 2 (Context-Free) in the Chomsky hierarchy.

A PDA is a finite-state machine augmented with an unbounded stack. Its transition function maps a triple (state, input_symbol, stack_top) to a pair (next_state, stack_ops) where stack_ops is the list of symbols pushed after popping the top of the stack.

The tape-based memory of TuringMachine and LinearBoundedAutomaton is not used. The PDA operates exclusively on its stack (self.stack) and on the input word (self.input_word / self.input_pos).

Parameters:

name (str) – Name of the automaton.
stack_alphabet (set | None) – Set of symbols allowed on the stack. The bottom-of-stack marker (bottom_symbol) is always included.
bottom_symbol (str) – Initial stack symbol (bottom-of-stack marker). Defaults to "Z".
accept (str) – Accepting state label. Defaults to "OK".
reject (str) – Rejecting state label. Defaults to "nOK".

stack

The stack. stack[-1] is the top.

Type:: list

stack_alphabet

The set of symbols allowed on the stack.

Type:: set

input_word

The input word currently loaded.

Type:: list

input_pos

Current read position in input_word.

Type:: int

register

Current state.

Type:: str

validation

Maps "accept" and "reject" to their labels.

Type:: dict

Note

Epsilon-transitions (input_symbol=None) are not implemented in v0.1.0. They are reserved for v0.3.0. Attempting to add one raises NotImplementedError.

Initializes the Linear Bounded Automaton with a given name, dimensional limits, and blank symbol.

Parameters:

name (str) – The name of the automaton.
tape_size (list) – A list of size limits for each dimension of the tape.
blank_symbol (str) – The blank symbol representing an empty tape cell.
movement (dict) – A dictionary of allowed movements.
register (str) – The current state of the automaton.
accept (str) – The accept state.
reject (str) – The reject state.

get_stack_alphabet() → set[source]

Return the stack alphabet.

Returns:: Set of symbols allowed on the stack.
Return type:: set
Raises:: ReadError – If the stack alphabet is empty.

push(symbol: Any) → None[source]

Push a symbol onto the top of the stack.

Parameters:: symbol (Any) – Symbol to push. Must be in the stack alphabet.
Raises:: AddError – If the symbol is not in the stack alphabet.

pop() → Any[source]

Pop the top symbol off the stack.

Returns:: The symbol that was on top.
Return type:: Any
Raises:: RemoveComponentError – If the stack is empty.

peek() → Any[source]

Return the top symbol without removing it.

Returns:: The symbol currently on top of the stack.
Return type:: Any
Raises:: RemoveComponentError – If the stack is empty.

reset_stack() → None[source]: Reset the stack to its initial state (bottom marker only).

set_input(word: List[Any]) → None[source]

Load an input word and reset the read head to position 0.

All symbols in word must be in the input alphabet (self.grammar.alphabet).

Parameters:: word (List[Any]) – Sequence of input symbols.
Raises:: ReadError – If any symbol is not in the input alphabet.

set_register(state: str) → None[source]

Set the current state of the automaton.

If this is the first call, the state also becomes the grammar start symbol.

Parameters:: state (str) – State label.

add_transition(state_from: str, input_symbol: Any, stack_top: Any, state_to: str, stack_ops: List[Any]) → None[source]

Add a transition rule to the PDA.

A transition is a 5-tuple:

(state_from, input_symbol, stack_top, state_to, stack_ops)

state_from: state before the transition.
input_symbol: input symbol consumed. None is reserved for epsilon-transitions (v0.3.0) and raises NotImplementedError here.
stack_top: symbol that must be on top of the stack (will be popped).
state_to: state after the transition.
stack_ops: list of symbols pushed after popping stack_top. [] = pure pop; [X] = replace top with X; [X, Y] = pop then push Y, then X (X ends up on top).

Parameters:

state_from (str) – Source state.
input_symbol (Any) – Input symbol consumed by this transition.
stack_top (Any) – Expected top-of-stack symbol (will be popped).
state_to (str) – Target state.
stack_ops (List[Any]) – Symbols to push after popping, leftmost ends on top.

Raises:

NotImplementedError – If input_symbol is None (epsilon-transitions are reserved for v0.3.0).
ReadError – If input_symbol is not in the input alphabet, or stack_top / any symbol in stack_ops is not in the stack alphabet.
AddError – If an identical transition already exists.

step() → None[source]

Execute one step of the PDA.

Looks for a matching transition (register, current_input, stack_top) in self.grammar.rules. On match:

Pop the stack top.
Push stack_ops in reverse order (so the leftmost symbol in stack_ops ends up on top).
Advance the input position by 1.
Update self.register to the target state.

Raises:

ReadError – If the stack is empty when trying to read the top.
Exception – If no matching transition is found.

validate(word: List[Any]) → bool[source]

Determine whether word is accepted by the PDA.

Acceptance is by empty stack: the word is accepted if, after consuming all input symbols, the stack is empty (the bottom marker has been popped).

The automaton is reset (stack, register, input) before running.

Parameters:

word (List[Any]) – Input word to validate.

Raises:

ValidationError – If the automaton is not configured (no start state, no terminals, no transitions).
ValidationError – If any symbol in word is not in the input alphabet.

Returns:

True if word is accepted, False otherwise.

Return type:

bool

set_tape(*args, **kwargs)[source]: Not applicable to PDA. Use set_input() instead.

read()[source]: Not applicable to PDA. Use peek() or _current_input() instead.

write(symbol)[source]: Not applicable to PDA. Use push() instead.

move(direction)[source]: Not applicable to PDA. The input head advances automatically in step().

Note

FiniteStateAutomaton (Type 3 — Regular) is planned for v0.2.0.