from __future__ import annotations
from collections.abc import Iterable, Iterator
class TransitionFunction:
"""A finite state machine transition function.
Parameters
----------
transition_graph : dict[tuple[str, str], set[str]]
Mapping from (state, symbol) pairs to sets of target states.
Attributes
----------
transition_graph : dict[tuple[str, str], set[str]]
The underlying transition graph.
"""
def __init__(
self,
transition_graph: dict[tuple[str, str], str | set[str]],
) -> None:
self._transition_graph: dict[tuple[str, str], set[str]] = {
key: {targets} if isinstance(targets, str) else set(targets)
for key, targets in transition_graph.items()
}
def __call__(self, state: str, symbol: str) -> set[str]:
"""Return the set of states reachable from state on symbol.
Parameters
----------
state : str
The source state.
symbol : str
The input symbol.
Returns
-------
set[str]
The set of target states, or an empty set if undefined.
"""
try:
return self._transition_graph[(state, symbol)]
except KeyError:
return set()
def __or__(self, other: TransitionFunction) -> TransitionFunction:
"""Merge two transition functions.
Parameters
----------
other : TransitionFunction
The transition function to merge with.
Returns
-------
TransitionFunction
A new transition function combining both graphs.
"""
merged = {
key: set(targets)
for key, targets in self._transition_graph.items()
}
for key, targets in other._transition_graph.items():
merged.setdefault(key, set()).update(targets)
return TransitionFunction(merged)
def add_transitions(
self,
transition_graph: dict[tuple[str, str], str | set[str]],
) -> None:
"""Add new transitions to the graph.
Parameters
----------
transition_graph : dict[tuple[str, str], set[str]]
Transitions to add.
"""
for key, targets in transition_graph.items():
normalized = {targets} if isinstance(targets, str) else set(targets)
self._transition_graph.setdefault(key, set()).update(normalized)
def validate(self, alphabet: set[str], states: set[str]) -> None:
"""Validate the transition function against an alphabet and state set.
Parameters
----------
alphabet : set[str]
The valid alphabet symbols.
states : set[str]
The valid states.
"""
self._validate_input_values(alphabet, states)
self._validate_output_values(states)
def _validate_input_values(
self,
alphabet: set[str],
states: set[str],
) -> None:
"""Check that all input symbols and states are valid."""
for state, symbol in self._transition_graph:
if symbol not in alphabet:
msg = ('all input symbols in transition function '
'must be in alphabet')
raise ValueError(msg)
if state not in states:
msg = ('all input states in transition function '
'must be in set of states')
raise ValueError(msg)
def _validate_output_values(self, states: set[str]) -> None:
"""Check that all output states are in the state set."""
for out in self._transition_graph.values():
if not all(state in states for state in out):
msg = ('all output symbols in transition function '
'must be in states')
raise ValueError(msg)
@property
def transition_graph(self) -> dict[tuple[str, str], set[str]]:
"""The underlying transition graph."""
return self._transition_graph
class FiniteStateAutomaton:
"""A finite state automaton.
Parameters
----------
alphabet : set[str]
The input alphabet.
states : set[str]
The set of states.
initial_state : str
The start state.
final_states : set[str]
The set of accepting states.
transition_graph : TransitionFunction
The transition function mapping (state, symbol) to states.
"""
def __init__(
self,
alphabet: set[str],
states: set[str],
initial_state: str,
final_states: set[str],
transition_graph: dict[tuple[str, str], str | set[str]],
) -> None:
self._alphabet = set(alphabet) - {''}
self._states = set(states)
self._initial_state = initial_state
self._final_states = set(final_states)
self._transition_function = TransitionFunction(transition_graph)
self._validate_initial_state()
self._validate_final_states()
self._transition_function.validate(self._alphabet | {''}, self._states)
self._generator = self._build_generator()
def _validate_initial_state(self) -> None:
"""Check that the initial state belongs to the state set."""
if self._initial_state not in self._states:
raise ValueError('initial state must be in the state set')
def _validate_final_states(self) -> None:
"""Check that every final state belongs to the state set."""
if not self._final_states <= self._states:
raise ValueError('final states must be a subset of the state set')
def __iter__(self) -> FiniteStateAutomaton:
return self
def __next__(self) -> str:
return next(self._generator)
def _build_generator(self) -> Iterator[str]:
"""Enumerate accepted strings in increasing length."""
reverse_graph: dict[str, set[str]] = {
state: set() for state in self._states
}
for (source, _), targets in self._transition_function.transition_graph.items():
for target in targets:
reverse_graph[target].add(source)
productive = set(self._final_states)
worklist = list(productive)
while worklist:
target = worklist.pop()
for source in reverse_graph[target]:
if source not in productive:
productive.add(source)
worklist.append(source)
def epsilon_closure(states: Iterable[str]) -> set[str]:
closure = set(states)
pending = list(closure)
while pending:
state = pending.pop()
for target in self._transition_function(state, ''):
if target not in closure:
closure.add(target)
pending.append(target)
return closure
current = {
(state, '')
for state in epsilon_closure({self._initial_state})
if state in productive
}
emitted: set[str] = set()
while current:
accepted = sorted({
word
for state, word in current
if state in self._final_states and word not in emitted
})
for word in accepted:
emitted.add(word)
yield word
following: set[tuple[str, str]] = set()
for state, word in current:
for symbol in sorted(self._alphabet):
targets = self._transition_function(state, symbol)
for target in epsilon_closure(targets):
if target in productive:
following.add((target, word + symbol))
current = followingTwo equivalent definitions
Let’s now formalize the definition of a finite state automaton (FSA). There are two versions to consider: the Deterministic Finite State Automaton (DFA) and the Nondeterministic Finite State Automaton (NFA). Are these genuinely different grammar formalisms? We’ll show that they are weakly equivalent. That is, DFAs and NFAs generate exactly the same class of languages.
Deterministic Finite State Automaton (DFA)
A Deterministic Finite State Automaton (DFA) is a grammar with 5 components:
- A set of states \(Q\)
- An alphabet \(\Sigma\)
- A transition function \(\delta : Q \times \Sigma \rightarrow Q\)
- An initial state \(q_0 \in Q\)
- A set of final states \(F \subseteq Q\)
Nondeterministic Finite State Automaton (NFA)
A Nondeterministic Finite State Automaton (NFA) is also a grammar with 5 components:
- A set of states \(Q\)
- An alphabet \(\Sigma\)
- A transition function \(\delta : Q \times (\Sigma\,\color{red}{\cup \{\epsilon\}}) \rightarrow \color{red}{\mathcal{P}(Q)}\)
- An initial state \(q_0 \in Q\)
- A set of final states \(F \subseteq Q\)
What makes NFAs nondeterministic is that the transition function \(\delta\) can map a given state \(q\) and symbol \(\sigma\) to multiple states. That is, there are potentially multiple states to choose from when transitioning from \(q\) on \(\sigma\).
We often define and draw FSAs whose transition functions are partial. What happens when a transition is missing? We can make the function total by adding a sink state \(q_\text{sink} \not\in F\) and mapping every \(\langle q, \sigma \rangle\) pair for which \(\delta\) is undefined to \(q_\text{sink}\).
class TransitionFunction(TransitionFunction):
"""A finite state machine transition function with totalization.
Extends the base transition function with methods to check
totality and to totalize via a sink state.
Parameters
----------
transition_graph : dict[tuple[str, str], set[str]]
Mapping from (state, symbol) pairs to sets of target states.
"""
def istotalfunction(self, states: set[str], alphabet: set[str]) -> bool:
"""Check whether the transition function is total.
Parameters
----------
states : set[str]
The set of states.
alphabet : set[str]
The input alphabet.
Returns
-------
bool
True if every (state, symbol) pair is defined.
"""
return all(bool(self._transition_graph.get((s, a)))
for s in states
for a in alphabet)
def totalize(self, states: set[str], alphabet: set[str]) -> None:
"""Make the transition function total by adding a sink state.
Parameters
----------
states : set[str]
The set of states.
alphabet : set[str]
The input alphabet.
"""
surface_alphabet = alphabet - {''}
if not self.istotalfunction(states, surface_alphabet):
domain = {(s, a) for s in states for a in surface_alphabet}
sink_state = 'qsink'
while sink_state in states:
sink_state += 'sink'
states.add(sink_state)
for inp in domain:
if not self._transition_graph.get(inp):
self._transition_graph[inp] = {sink_state}
for symbol in surface_alphabet:
self._transition_graph[(sink_state, symbol)] = {sink_state}Totality and determinism are distinct. The method above fills every missing surface-symbol input, but it does not remove epsilon transitions or multiple targets from an NFA. A complete DFA must additionally have no epsilon transitions and exactly one target for every state-symbol pair.
As I mentioned, it turns out that these two ways of defining FSAs are at least weakly equivalent. That is, the class of languages generated by NFAs is the same as the class generated by DFAs; thus, both generate exactly the regular languages.
This is the same double-inclusion argument we used to prove the lookaround language equation. Let \(\mathcal{L}_{\mathrm{DFA}}\) be the set of languages recognized by DFAs and \(\mathcal{L}_{\mathrm{NFA}}\) the set recognized by NFAs. Converting every DFA to an equivalent NFA proves \(\mathcal{L}_{\mathrm{DFA}}\subseteq\mathcal{L}_{\mathrm{NFA}}\). Converting every NFA to an equivalent DFA proves the reverse inclusion. Once we have both, double inclusion gives equality of the two language classes.
DFAs are equivalent to NFAs
Every DFA can be converted to a weakly equivalent NFA. A DFA \(G = \langle Q, \Sigma, \delta, q_0, F \rangle\) can be converted to an NFA \(G' = \langle Q', \Sigma, \delta', q'_0, F' \rangle\) by defining the transition function of \(G'\) as \(\delta'(q,\sigma) \equiv \{\delta(q,\sigma)\}\). The new NFA simulates the DFA by giving itself no choice: every transition leads to the singleton containing the DFA’s next state.
Why does the conversion preserve the language? Fix an arbitrary string \(w=\sigma_1\ldots\sigma_n\). After reading the first \(i\) symbols, the NFA’s reachable-state set should be the singleton containing the DFA’s current state. This is the simulation invariant. At \(i=0\), both machines start at \(q_0\). Now suppose the DFA is in \(q\) and the NFA’s reachable set is \(\{q\}\) after \(i\) symbols. On \(\sigma_{i+1}\), the DFA moves to \(\delta(q,\sigma_{i+1})\), while the NFA moves to
\[\delta'(q,\sigma_{i+1})=\{\delta(q,\sigma_{i+1})\}.\]
Thus, the invariant holds after the next symbol. At \(i=n\), the DFA’s state belongs to \(F\) if and only if the NFA’s singleton reachable set intersects \(F'=F\). Hence the two machines agree on the arbitrary \(w\), and they recognize the same language.
class TransitionFunction(TransitionFunction):
"""A finite state machine transition function with determinism check.
Extends the transition function with a property to test whether
the automaton is deterministic.
Parameters
----------
transition_graph : dict[tuple[str, str], set[str]]
Mapping from (state, symbol) pairs to sets of target states.
"""
@property
def isdeterministic(self) -> bool:
"""Whether the transition function is deterministic.
Returns
-------
bool
True if no epsilon transitions exist and every input maps
to at most one state.
"""
has_epsilon = any(symb == '' for _, symb in self._transition_graph.keys())
all_singleton = all(len(v) < 2 for v in self._transition_graph.values())
return all_singleton and not has_epsilon
def is_total_dfa(self, states: set[str], alphabet: set[str]) -> bool:
"""Whether the graph is deterministic and complete."""
surface_alphabet = alphabet - {''}
return (self.isdeterministic
and all(len(self(state, symbol)) == 1
for state in states
for symbol in surface_alphabet))
def subset_label(states: frozenset[str]) -> str:
"""Serialize a subset injectively using length-prefixed state names."""
if not states:
return '∅'
return ''.join(f'{len(state)}:{state}' for state in sorted(states))
class FiniteStateAutomaton(FiniteStateAutomaton):
"""A finite state automaton with determinism check.
Parameters
----------
alphabet : set[str]
The input alphabet.
states : set[str]
The set of states.
initial_state : str
The start state.
final_states : set[str]
The set of accepting states.
transition_graph : TransitionFunction
The transition function.
"""
@property
def isdeterministic(self) -> bool:
"""Whether the automaton is deterministic.
Returns
-------
bool
True if the underlying transition function is deterministic.
"""
return self._transition_function.isdeterministic
@property
def is_total_dfa(self) -> bool:
"""Whether the automaton is deterministic and complete."""
return self._transition_function.is_total_dfa(
self._states, self._alphabet,
)NFAs are equivalent to DFAs
Every NFA can be converted to a weakly equivalent DFA.
For \(R\subseteq Q\), define its epsilon closure by finite paths:
\[ E(R)=\{q\in Q\mid \text{some finite epsilon-only path leads from a state in }R\text{ to }q\}. \]
The length-zero path ensures \(R\subseteq E(R)\). Equivalently, \(E(R)\) is the least fixed point of \(X\mapsto R\cup\bigcup_{q\in X}\delta(q,\epsilon)\). This definition remains well-founded when the NFA has epsilon cycles.
An NFA \(G = \langle Q, \Sigma, \delta, q_0, F \rangle\) can be converted to a DFA \(G' = \langle Q', \Sigma, \delta', q'_0, F' \rangle\) by defining:
- \(Q' = \mathcal{P}(Q)\)
- \(\delta'(R, \sigma) = E\left(\bigcup_{r\in R}\delta(r,\sigma)\right)\)
- \(q'_0 = E(\{q_0\})\)
- \(F' = \{R\;|\; \exists r \in R: r \in F\}\)
The new DFA simulates the NFA by tracking the set of states that the NFA could be in after producing or reading a given string. Remember that a state need not be an atomic object such as a character or number. It can be a set, string, or even a tree, as long as the automaton still has only finitely many states.
Now we need to show that this set-valued state contains exactly the right possibilities. Let \(\operatorname{Reach}_G(w)\) be the set of all NFA states reachable after consuming exactly \(w\), allowing epsilon transitions before the first symbol, between symbols, and after the last symbol. After the new DFA reads any prefix \(w\), its single current state should be the subset \(\operatorname{Reach}_G(w)\). This is the reachable-subset invariant.
Start with \(w=\epsilon\). The new initial state \(q'_0\) is exactly the epsilon closure of \(q_0\), so the invariant holds before any input is consumed. Now fix an arbitrary \(w\) and suppose the DFA is in \(R=\operatorname{Reach}_G(w)\). After reading a symbol \(\sigma\), the NFA may start in any \(r\in R\), take a \(\sigma\)-transition, and then take any number of epsilon transitions. The definition
\[\delta'(R,\sigma)=E\left(\bigcup_{r\in R}\delta(r,\sigma)\right)\]
collects exactly those possibilities. It includes no other state, and it omits none. Thus, \(\delta'(R,\sigma)=\operatorname{Reach}_G(w\sigma)\), which preserves the invariant.
Finally, the NFA accepts \(w\) if and only if at least one state in \(\operatorname{Reach}_G(w)\) belongs to \(F\). By the reachable-subset invariant, this holds if and only if the DFA’s current subset belongs to \(F'\). The machines thus agree on every string.
For instance, suppose \(q_0\xrightarrow{\epsilon}q_1\), \(q_1\xrightarrow{a}q_1\), \(q_1\xrightarrow{a}q_2\), and only \(q_2\) is final. Before any input, the NFA could be in \(q_0\) or \(q_1\), so the DFA begins in \(\{q_0,q_1\}\). After a, the NFA could be in \(q_1\) or \(q_2\), so the DFA moves to \(\{q_1,q_2\}\). That subset is final because it contains \(q_2\). This is exactly what the invariant records: one DFA state represents all simultaneous NFA possibilities.
from itertools import chain, combinations
def powerset[T](iterable: Iterable[T]) -> Iterator[tuple[T, ...]]:
"""Generate all subsets of an iterable.
From the itertools recipes:
https://docs.python.org/3/library/itertools.html#recipes
Parameters
----------
iterable
The collection to compute subsets of.
Returns
-------
itertools.chain
All subsets, from empty to full.
"""
s = list(iterable)
return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
class TransitionFunction(TransitionFunction):
"""A finite state machine transition function with epsilon closure.
Extends the transition function with epsilon-closure computation
and NFA-to-DFA determinization.
Parameters
----------
transition_graph : dict[tuple[str, str], set[str]]
Mapping from (state, symbol) pairs to sets of target states.
"""
def epsilon_closure(self, states: Iterable[str]) -> set[str]:
"""Return endpoints of finite epsilon paths from `states`."""
closure = set(states)
worklist = list(closure)
while worklist:
state = worklist.pop()
for target in self(state, ''):
if target not in closure:
closure.add(target)
worklist.append(target)
return closure
def move(self, states: Iterable[str], symbol: str) -> set[str]:
"""Consume one symbol and then take epsilon closure."""
direct = {target
for state in states
for target in self(state, symbol)}
return self.epsilon_closure(direct)
class FiniteStateAutomaton(FiniteStateAutomaton):
"""A finite state automaton with subset-construction determinization.
Parameters
----------
alphabet : set[str]
The input alphabet.
states : set[str]
The set of states.
initial_state : str
The start state.
final_states : set[str]
The set of accepting states.
transition_graph : TransitionFunction
The transition function.
"""
def determinize(self) -> FiniteStateAutomaton:
"""Determinize the FSA using the standard subset construction.
Returns
-------
FiniteStateAutomaton
A weakly equivalent deterministic FSA.
"""
alphabet = self._alphabet - {''}
# Each DFA state is a frozenset of NFA states; explore
# reachable states breadth-first from the initial state
new_init_frozen = frozenset(
self._transition_function.epsilon_closure({self._initial_state})
)
worklist = [new_init_frozen]
visited = set()
new_transition = {}
while worklist:
current = worklist.pop()
if current in visited:
continue
visited.add(current)
for a in alphabet:
target_frozen = frozenset(
self._transition_function.move(current, a)
)
src_label = subset_label(current)
tgt_label = subset_label(target_frozen)
new_transition[(src_label, a)] = {tgt_label}
if target_frozen not in visited:
worklist.append(target_frozen)
new_states = {subset_label(s) for s in visited}
new_final = {subset_label(s) for s in visited
if any(t in s for t in self._final_states)}
return FiniteStateAutomaton(alphabet, new_states,
subset_label(new_init_frozen),
new_final, new_transition)
@property
def isdeterministic(self) -> bool:
"""Whether the automaton is deterministic.
Returns
-------
bool
True if the underlying transition function is deterministic.
"""
return self._transition_function.isdeterministicThe tests below check transition merging, unambiguous subset names, sink-state totalization, and epsilon cycles.
left = TransitionFunction({('q', 'a'): {'r'}})
right = TransitionFunction({('q', 'a'): {'s'}})
assert (left | right)('q', 'a') == {'r', 's'}
assert subset_label(frozenset({'a_b', 'c'})) != subset_label(
frozenset({'a', 'b_c'}),
)
states = {'q'}
totalized = TransitionFunction({})
totalized.totalize(states, {'a'})
sink = next(iter(states - {'q'}))
assert totalized('q', 'a') == {sink}
assert totalized(sink, 'a') == {sink}
assert totalized.is_total_dfa(states, {'a'})
epsilon_cycle = FiniteStateAutomaton(
{'a'}, {'q0', 'q1'}, 'q0', {'q1'},
{
('q0', ''): {'q0', 'q1'},
('q1', 'a'): {'q1'},
},
)
cycle_dfa = epsilon_cycle.determinize()
assert cycle_dfa.is_total_dfa