1.2. Grammar as a Data Structure¶

In fsm-tools, a grammar is not merely a type annotation or a string constant — it is a full Python object, instantiated and owned by each Automaton instance. This design follows directly from the formal definition of a grammar in language theory (see Formal definition).

1.2.1. Formal definition¶

A grammar \(G\) is a quadruple \(G = (N,\ \Sigma,\ P,\ S)\) where:

\(N\) is a finite set of non-terminal symbols (states).
\(\Sigma\) is a finite set of terminal symbols (the alphabet), disjoint from \(N\).
\(P\) is a finite set of production rules.
\(S \in N\) is the start symbol.

The nature of \(P\) — what forms a valid production rule — is what distinguishes the four levels of the Chomsky hierarchy from one another.

1.2.2. Implementation¶

The Grammar class maps directly onto this quadruple:

Formal component	Attribute	Description
\(N\)	`grammar.states`	Set of non-terminal symbols (automaton states).
\(\Sigma\)	`grammar.alphabet`	Set of terminal symbols (input alphabet).
\(P\)	`grammar.rules`	List of production rules (format depends on automaton type).
\(S\)	`grammar.start`	Start symbol — the initial state of the automaton.

1.2.3. Design principle¶

The Grammar object is owned by its automaton. All mutations go through the Automaton API methods (add_terminals, add_non_terminals, add_rules, …). Direct access to automaton.grammar.alphabet is technically possible but discouraged — the automaton API is the stable contract.

from fsm_tools import TuringMachine

tm = TuringMachine(name="example", chomsky="Recursively Enumerable")
tm.add_terminals("a", "b")       # modifies grammar.alphabet
tm.add_non_terminals("q0", "q1") # modifies grammar.states

print(tm.grammar.alphabet)  # {'a', 'b', '_'}
print(tm.grammar.states)    # {'q0', 'q1', 'OK', 'nOK'}

Note

The blank symbol (_ by default for TuringMachine) is added to the alphabet automatically at initialisation.