A finite state automaton is a model of the behaviour of a system that remembers one thing only: which of a finite number of states it is in. At each input it changes state according to a fixed rule, and this is enough to answer questions about behaviour with a search in a graph instead of a discussion. A shopping cart can go from WITH_ITEMS to CHECKOUT but not directly to COMPLETE; you can ask whether there is a state from which you never leave, or whether a certain state is reachable only by passing through another. These are the questions of formal methods, and here they find an answer with programs of a few dozen lines. The prerequisite is the logic of the previous article.
What an automaton is: five components and a cart
An automaton is a quintuple (Q, Σ, δ, q₀, F), and for each component the cart provides the example.
Q: the finite set of states, hereEMPTY,WITH_ITEMS,CHECKOUT,PAYMENT,COMPLETE,CANCELLED.Σ: the alphabet of inputs, hereadd,remove,checkout,pay,outcome_ok,outcome_ko,cancel.δ: the transition function, which from a state and an input gives the new state.q₀: the initial state,EMPTY.F: the accepting states, here onlyCOMPLETE.
A state is not a variable of the code but the combination of values that distinguishes different future behaviours: two situations with the same future behaviour are the same state, even if the memory of the program has different contents. In the program δ is a partial function: a missing (state, input) pair means that the input is not allowed there, and the word is rejected. The program simulates three sequences, then uses a breadth-first search to find the reachable states and the states with no exits, and checks a safety property by removing a state from the graph.
from collections import deque
# Automaton (Q, Sigma, delta, q0, F) of the cart. delta is a PARTIAL function:
# a missing (state, input) pair means "input not allowed in this state".
Q = {"EMPTY", "WITH_ITEMS", "CHECKOUT", "PAYMENT", "COMPLETE", "CANCELLED"}
SIGMA = {"add", "remove", "checkout", "pay", "outcome_ok", "outcome_ko", "cancel"}
DELTA = {
("EMPTY", "add"): "WITH_ITEMS",
("WITH_ITEMS", "add"): "WITH_ITEMS",
("WITH_ITEMS", "remove"): "WITH_ITEMS",
("WITH_ITEMS", "checkout"): "CHECKOUT",
("WITH_ITEMS", "cancel"): "CANCELLED",
("CHECKOUT", "pay"): "PAYMENT",
("CHECKOUT", "cancel"): "CANCELLED",
("PAYMENT", "outcome_ok"): "COMPLETE",
("PAYMENT", "outcome_ko"): "CHECKOUT",
}
Q0, F = "EMPTY", {"COMPLETE"}
def accepts(word):
state = Q0
for symbol in word:
if (state, symbol) not in DELTA:
return False # input not allowed: the word is rejected
state = DELTA[state, symbol]
return state in F
def reachable(delta, q0, forbidden=frozenset()):
seen, queue = {q0}, deque([q0])
while queue:
q = queue.popleft()
for (p, _), r in delta.items():
if p == q and r not in seen and r not in forbidden:
seen.add(r)
queue.append(r)
return seen
print("regular order:", accepts(["add", "checkout", "pay", "outcome_ok"]))
print("payment without checkout:", accepts(["add", "pay", "outcome_ok"]))
print("payment declined and retried:",
accepts(["add", "checkout", "pay", "outcome_ko", "pay", "outcome_ok"]))
R = reachable(DELTA, Q0)
print("\nreachable from EMPTY:", sorted(R))
print("not reachable:", sorted(Q - R))
# Deadlock: reachable state, not accepting, with no outgoing transitions.
with_exits = {p for (p, _) in DELTA}
print("states without exits:", sorted(R - with_exits), "-> of which non-accepting:",
sorted((R - with_exits) - F))
# Safety: "COMPLETE is never reached without passing through PAYMENT".
# Remove PAYMENT from the graph and see whether COMPLETE is still reachable.
without_payment = reachable(DELTA, Q0, forbidden={"PAYMENT"})
print("COMPLETE reachable while avoiding PAYMENT:", "COMPLETE" in without_payment)
# Output:
# regular order: True
# payment without checkout: False
# payment declined and retried: True
#
# reachable from EMPTY: ['CANCELLED', 'CHECKOUT', 'COMPLETE', 'EMPTY', 'PAYMENT', 'WITH_ITEMS']
# not reachable: []
# states without exits: ['CANCELLED', 'COMPLETE'] -> of which non-accepting: ['CANCELLED']
# COMPLETE reachable while avoiding PAYMENT: False
The first sequence is accepted, the second (paying without going through checkout) is rejected because (WITH_ITEMS, pay) is not in DELTA, the third shows that a declined payment brings you back to checkout and you can try again. All six states are reachable. The states with no exits are two: COMPLETE, which is accepting, and CANCELLED, which the check flags as a possible deadlock because it is not accepting. In this model it is instead an intended outcome, so the right fix is to declare it terminal (or to add the exits if a cancelled order can in fact be reopened): the check does not decide for you, it forces you to choose. The last line verifies the property "COMPLETE is never reached without passing through PAYMENT": removing PAYMENT from the graph, COMPLETE becomes unreachable.
DFA and NFA: determinism, subsets, explosion
In a deterministic automaton (DFA) every (state, input) pair leads to a single state. In a non-deterministic one (NFA) it can lead to zero, one or more states, and the word is accepted if at least one of the paths ends in an accepting state. Non-determinism is not randomness: it is a compact way of describing an alternative. Rabin and Scott, in 1959, introduced NFAs and showed that they can be simulated with DFAs in which each state corresponds to a set of states of the NFA: this is the subset construction (a note reported by the article by Russ Cox cited in the sources).
The program that follows applies it to the expression (a|b)*abb (any sequence of a and b that ends with abb): a 4-state NFA, the resulting DFA, the comparison with Python's re module on all the 2047 strings of length 0 to 10, and a family of NFAs, "the n-th symbol from the end is a", to see how much the DFA grows. The function minimum counts the states of the minimal DFA with partition refinement: two states stay distinct as long as there is a continuation that one accepts and the other does not.
import re
from itertools import product
def nfa_from_suffix(n):
"""NFA for (a|b)*a(a|b)^(n-1): 'the n-th symbol from the end is a'."""
delta = {(0, "a"): {0, 1}, (0, "b"): {0}}
for i in range(1, n):
for c in "ab":
delta[(i, c)] = {i + 1}
return delta, 0, {n}
NFA_ABB = ({(0, "a"): {0, 1}, (0, "b"): {0}, (1, "b"): {2}, (2, "b"): {3}}, 0, {3})
def simulate_nfa(nfa, word):
delta, q0, finals = nfa
active = {q0}
for c in word:
active = set().union(*(delta.get((q, c), set()) for q in active))
return bool(active & finals)
def subsets(nfa, alphabet="ab"):
"""Subset construction: each DFA state is a set of NFA states."""
delta, q0, finals = nfa
start = frozenset({q0})
dfa, todo, seen = {}, [start], {start}
while todo:
S = todo.pop()
for c in alphabet:
T = frozenset(set().union(*(delta.get((q, c), set()) for q in S)))
dfa[S, c] = T
if T not in seen:
seen.add(T)
todo.append(T)
return dfa, start, {S for S in seen if S & finals}
def simulate_dfa(dfa, word):
d, start, finals = dfa
S = start
for c in word:
S = d[S, c]
return S in finals
def minimum(dfa, alphabet="ab"):
"""Partition refinement (Moore): number of states of the minimal DFA."""
d, start, finals = dfa
states = {s for s, _ in d}
cls = {s: int(s in finals) for s in states}
while True:
signature = {s: (cls[s], tuple(cls[d[s, c]] for c in alphabet)) for s in states}
numbers = {f: i for i, f in enumerate(sorted(set(signature.values())))}
new = {s: numbers[signature[s]] for s in states}
if len(set(new.values())) == len(set(cls.values())):
return len(set(new.values()))
cls = new
# 1. (a|b)*abb: 4-state NFA, subset DFA, comparison with re
dfa = subsets(NFA_ABB)
print("subset DFA: states", len({s for s, _ in dfa[0]}), "- minimal:", minimum(dfa))
for S in sorted({s for s, _ in dfa[0]}, key=lambda s: (len(s), sorted(s))):
print(" ", sorted(S), "final" if S in dfa[2] else "",
{c: sorted(dfa[0][S, c]) for c in "ab"})
disagreements = 0
total = 0
for n in range(0, 11):
for p in product("ab", repeat=n):
w = "".join(p)
total += 1
expected = re.fullmatch("(a|b)*abb", w) is not None
if simulate_nfa(NFA_ABB, w) != expected or simulate_dfa(dfa, w) != expected:
disagreements += 1
print("strings checked (length 0..10):", total, "- disagreements with re:", disagreements)
# 2. When the DFA explodes: 'the n-th symbol from the end is a'
print("\nn NFA states DFA states minimal DFA 2**n")
for n in range(1, 11):
nfa = nfa_from_suffix(n)
d = subsets(nfa)
print(f"{n:<3} {n + 1:<11} {len({s for s, _ in d[0]}):<11} {minimum(d):<12} {2 ** n}")
# Output:
# subset DFA: states 4 - minimal: 4
# [0] {'a': [0, 1], 'b': [0]}
# [0, 1] {'a': [0, 1], 'b': [0, 2]}
# [0, 2] {'a': [0, 1], 'b': [0, 3]}
# [0, 3] final {'a': [0, 1], 'b': [0]}
# strings checked (length 0..10): 2047 - disagreements with re: 0
#
# n NFA states DFA states minimal DFA 2**n
# 1 2 2 2 2
# 2 3 4 4 4
# 3 4 8 8 8
# 4 5 16 16 16
# 5 6 32 32 32
# 6 7 64 64 64
# 7 8 128 128 128
# 8 9 256 256 256
# 9 10 512 512 512
# 10 11 1024 1024 1024
The subset DFA has 4 states, and they are already minimal. The states are sets such as [0, 1]: after reading an a the automaton can be in 0 (the a did not belong to the suffix) or in 1 (the a is the beginning of abb), and the DFA keeps track of both hypotheses together. On 2047 strings there is no disagreement with re, for either the NFA or the DFA. The final table is the point to remember: for the "n-th symbol from the end" family the DFA has 2n states and, as the minimum column shows, it cannot be reduced. The explosion is a property of the language, not of a badly done construction; for n = 11 the same function gives 2048.
Why the NFA is still convenient
Keeping the set of active states and advancing it at every symbol simulates the NFA without building the DFA. Cox describes in his article on regular expressions a pathological case, a?nan on an, in which Perl's backtracking approach takes over sixty seconds for n = 29 and the simulation of the NFA twenty microseconds. The program below redoes the comparison with the re engine of Python 3.14.4 and a simulation with a set of active states; the times change from one machine and one run to another, so the block reports one run and the text refers only to the order of magnitude.
import re
import time
def nfa_a_n(n):
"""Simulate a?^n a^n with the set of active states (Thompson/Cox algorithm)."""
string = "a" * n
# states 0..2n; the first n are 'a?' (can be skipped), the other n are mandatory 'a'
def closure(S):
S = set(S)
for i in range(n):
if i in S:
S.add(i + 1)
return S
active = closure({0})
for _ in string:
nxt = set()
for q in active:
if q < 2 * n:
nxt.add(q + 1)
active = closure(nxt)
return 2 * n in active
for n in (16, 18, 20, 22, 24):
regex = re.compile("a?" * n + "a" * n)
t0 = time.perf_counter()
r1 = regex.fullmatch("a" * n) is not None
t1 = time.perf_counter()
r2 = nfa_a_n(n)
t2 = time.perf_counter()
print(f"n={n}: re={t1 - t0:.4f} s NFA simulation={t2 - t1:.6f} s same outcome={r1 == r2}")
# Output:
# n=16: re=0.0027 s NFA simulation=0.000053 s same outcome=True
# n=18: re=0.0231 s NFA simulation=0.000073 s same outcome=True
# n=20: re=0.1195 s NFA simulation=0.000092 s same outcome=True
# n=22: re=0.3302 s NFA simulation=0.000094 s same outcome=True
# n=24: re=1.8475 s NFA simulation=0.000104 s same outcome=True
Every time n grows by 2 the time of re is multiplied by about 4 and reaches around a second at n = 24, while the simulation of the NFA stays in the order of tens or hundreds of microseconds and the outcome coincides on all the lines. It is the same exponential growth that Cox measures in Perl, observed here on a different engine. The practical conclusion: if you apply regular expressions to texts you do not control, a backtracking engine can have exponential times on crafted inputs, while the simulation with a set of states, in the program, costs as a function of the length of the input and the number of states (here 2n).
What a DFA cannot count: the pumping lemma
Not all languages are regular. The pumping lemma gives a necessary condition: if L is regular there is a length p such that every word w of L with |w| ≥ p can be written w = xyz with |y| ≥ 1, |xy| ≤ p, and xyiz in L for every i ≥ 0. The idea is the pigeonhole principle: a DFA with p states that reads p symbols visits a state twice, and the stretch between the two visits, y, can be repeated or removed without changing the outcome.
For L = {anbn} the proof by contradiction is short. Suppose L is regular with constant p and take w = apbp. Since |xy| ≤ p, y contains only a's, that is y = aj with j ≥ 1. Then xy2z = ap+jbp has more a's than b's and is not in L: contradiction. Anyone recognizing balanced parentheses or nested tags therefore needs more than a DFA, at least a pushdown automaton.
The program makes two checks. The first takes the DFA of (a|b)*abb (p = 4) and, for some words, builds the decomposition xyz from the first state that repeats and checks xyiz for i from 0 to 5. The second enumerates all the DFAs with k states over {a, b} (k from 1 to 4, over a million in total) and looks for the largest n for which some DFA agrees with anbn on all the strings up to length 2n.
from itertools import product
# --- Part 1: the xyz scheme on a real DFA (strings ending with 'abb') ---
DELTA = {(0, "a"): 1, (0, "b"): 0, (1, "a"): 1, (1, "b"): 2,
(2, "a"): 1, (2, "b"): 3, (3, "a"): 1, (3, "b"): 0}
FINALS, P = {3}, 4 # P = number of states
def accepts(w):
q = 0
for c in w:
q = DELTA[q, c]
return q in FINALS
def decompose(w):
"""First state visited twice in the first P symbols: x, y, z come from there."""
q, seen = 0, {0: 0}
for i, c in enumerate(w[:P], start=1):
q = DELTA[q, c]
if q in seen:
j = seen[q]
return w[:j], w[j:i], w[i:]
seen[q] = i
raise ValueError("a word of length at least P is needed")
print("word x | y | z xy^i z accepted for i=0..5")
for w in ("aabb", "babb", "aaabb", "bbbabb"):
if len(w) < P:
continue
x, y, z = decompose(w)
outcomes = [accepts(x + y * i + z) for i in range(6)]
print(f"{w:<11} {x!r:<3} {y!r:<4} {z!r:<8} {outcomes}")
# --- Part 2: no DFA with k states recognizes a^n b^n for large n ---
def in_L(w):
n = len(w) // 2
return w == "a" * n + "b" * n
def strings_up_to(m):
return ["".join(p) for length in range(m + 1) for p in product("ab", repeat=length)]
def dfa_k_states(k):
"""All DFAs with k states over {a,b}, initial state 0: k**(2k) * 2**k."""
for table in product(range(k), repeat=2 * k):
for finals in range(2 ** k):
yield table, finals
def run(table, finals, w):
q = 0
for c in w:
q = table[2 * q + (c == "b")]
return bool(finals >> q & 1)
print("\nk DFAs examined largest n such that a DFA with k states agrees with a^n b^n")
for k in range(1, 5):
survivors = list(dfa_k_states(k))
examined = len(survivors)
n = -1
while True:
candidates = [s for s in strings_up_to(2 * (n + 1)) if len(s) >= 2 * n + 1 or n < 0]
new = [(t, f) for t, f in survivors
if all(run(t, f, w) == in_L(w) for w in candidates)]
if not new:
break
survivors, n = new, n + 1
print(f"{k} {examined:<15} {n}")
# Output:
# word x | y | z xy^i z accepted for i=0..5
# aabb 'a' 'a' 'bb' [True, True, True, True, True, True]
# babb '' 'b' 'abb' [True, True, True, True, True, True]
# aaabb 'a' 'a' 'abb' [True, True, True, True, True, True]
# bbbabb '' 'b' 'bbabb' [True, True, True, True, True, True]
#
# k DFAs examined largest n such that a DFA with k states agrees with a^n b^n
# 1 2 0
# 2 64 0
# 3 5832 1
# 4 1048576 1
In the four decompositions, xyiz is accepted for every i tried, as the lemma predicts. The table confirms the pigeonhole argument with numbers: with 1 or 2 states no DFA manages to recognize even ab (n = 0), with 3 or 4 states you get to n = 1 and not to n = 2. The lemma guarantees failure for n ≥ k; the enumeration finds it earlier (with 4 states already at n = 2) because the threshold n ≥ k of the lemma is enough to guarantee failure, but it is not the tightest one. The enumeration covers only k ≤ 4: it is not a proof for every k, which remains the proof by contradiction written above.
Automata with output: Mealy and Moore
A DFA says yes or no. To translate an input into an output you need automata with output. In a Mealy machine the output is attached to the transition, in a Moore machine to the state. The example is an edge detector: it emits 1 when the current bit differs from the previous one (at the start the previous one is 0). In the Mealy version 2 states are enough, one for the last bit read; the Moore version is obtained by taking as state the pair (Mealy state, last output), and the program builds exactly this and compares it with the Mealy one on all the strings up to length 10.
from itertools import product
# Mealy: the output sits on the transition. State = last bit read.
# Output 1 when the current bit differs from the previous one (at the start the previous is 0).
MEALY = {(p, b): (b, int(b != p)) for p in (0, 1) for b in (0, 1)} # (state, input) -> (state', output)
def run_mealy(w):
q, out = 0, []
for b in w:
q, o = MEALY[q, b]
out.append(o)
return out
# Mealy -> Moore construction: the Moore state is the pair (Mealy state, output just produced).
MOORE_DELTA, MOORE_OUTPUT = {}, {}
todo, seen = [(0, 0)], {(0, 0)} # (initial state, initial output 0)
while todo:
s = todo.pop()
MOORE_OUTPUT[s] = s[1]
for b in (0, 1):
q2, o = MEALY[s[0], b]
t = (q2, o)
MOORE_DELTA[s, b] = t
if t not in seen:
seen.add(t)
todo.append(t)
def run_moore(w):
s, out = (0, 0), [0] # the output of the initial state comes out before any input
for b in w:
s = MOORE_DELTA[s, b]
out.append(MOORE_OUTPUT[s])
return out
different = sum(run_mealy(w) != run_moore(w)[1:]
for n in range(11) for w in product((0, 1), repeat=n))
print("Mealy states: 2 - reachable Moore states:", len(seen), sorted(seen))
print("input 0110100 -> Mealy", run_mealy((0, 1, 1, 0, 1, 0, 0)))
print(" -> Moore", run_moore((0, 1, 1, 0, 1, 0, 0)))
print("strings up to length 10 with different outputs (Moore without the first symbol):", different)
# Output:
# Mealy states: 2 - reachable Moore states: 4 [(0, 0), (0, 1), (1, 0), (1, 1)]
# input 0110100 -> Mealy [0, 1, 0, 1, 1, 1, 0]
# -> Moore [0, 0, 1, 0, 1, 1, 1, 0]
# strings up to length 10 with different outputs (Moore without the first symbol): 0
The reachable states of the Moore version are 4 against the 2 of the Mealy: output in the state costs extra states. The Moore machine produces an initial output before reading any input (the output of the initial state), so on the input 0110100 its output has 8 values against the 7 of the Mealy and coincides with it after the first symbol. On all the 2047 strings up to length 10 the number of different outputs is zero, once that first symbol is removed. The choice between the two forms is one of convenience: the Mealy is more compact, the Moore has the output tied to the state and is therefore simpler to read on the diagram.
A real automaton: the states of TCP according to RFC 9293
Section 3.3.2 of RFC 9293 lists the eleven states of a TCP connection (LISTEN, SYN-SENT, SYN-RECEIVED, ESTABLISHED, FIN-WAIT-1, FIN-WAIT-2, CLOSE-WAIT, CLOSING, LAST-ACK, TIME-WAIT and CLOSED, the latter defined as fictional because it stands for the absence of a connection) and draws the transitions in Figure 5. The text warns that the diagram is only a summary and not the complete specification, and Note 3 specifies that the transitions due to an RST, which can arrive in any state, are not drawn. The program encodes the 20 arrows of the figure plus the transition of Note 2 (from FIN-WAIT-1 to TIME-WAIT) and applies the same checks as the cart.
from collections import deque
# Transitions of Figure 5 of RFC 9293 plus Note 2 (FIN-WAIT-1 -> TIME-WAIT).
# Format: (state, event) -> state.
T = {
("CLOSED", "passive OPEN"): "LISTEN",
("CLOSED", "active OPEN / snd SYN"): "SYN-SENT",
("LISTEN", "rcv SYN / snd SYN,ACK"): "SYN-RCVD",
("LISTEN", "SEND / snd SYN"): "SYN-SENT",
("LISTEN", "CLOSE"): "CLOSED",
("SYN-SENT", "CLOSE"): "CLOSED",
("SYN-SENT", "rcv SYN / snd SYN,ACK"): "SYN-RCVD",
("SYN-SENT", "rcv SYN,ACK / snd ACK"): "ESTABLISHED",
("SYN-RCVD", "rcv ACK of SYN"): "ESTABLISHED",
("SYN-RCVD", "CLOSE / snd FIN"): "FIN-WAIT-1",
("SYN-RCVD", "rcv RST (note 1)"): "LISTEN",
("ESTABLISHED", "CLOSE / snd FIN"): "FIN-WAIT-1",
("ESTABLISHED", "rcv FIN / snd ACK"): "CLOSE-WAIT",
("FIN-WAIT-1", "rcv ACK of FIN"): "FIN-WAIT-2",
("FIN-WAIT-1", "rcv FIN / snd ACK"): "CLOSING",
("FIN-WAIT-1", "rcv FIN and ACK of FIN (note 2)"): "TIME-WAIT",
("FIN-WAIT-2", "rcv FIN / snd ACK"): "TIME-WAIT",
("CLOSING", "rcv ACK of FIN"): "TIME-WAIT",
("CLOSE-WAIT", "CLOSE / snd FIN"): "LAST-ACK",
("LAST-ACK", "rcv ACK of FIN"): "CLOSED",
("TIME-WAIT", "Timeout=2MSL"): "CLOSED",
}
STATES = {s for s, _ in T} | set(T.values())
def shortest_path(src, dst, forbidden=frozenset()):
"""BFS: the shortest sequence of events from `src` to `dst`, avoiding `forbidden`."""
queue, parent = deque([src]), {src: None}
while queue:
q = queue.popleft()
if q == dst:
steps = []
while parent[q]:
q, event = parent[q]
steps.append(event)
return steps[::-1]
for (p, ev), r in T.items():
if p == q and r not in parent and r not in forbidden:
parent[r] = (q, ev)
queue.append(r)
return None
print("states:", len(STATES), "- transitions:", len(T))
print("unreachable from CLOSED:", sorted(s for s in STATES if shortest_path("CLOSED", s) is None))
print("without outgoing transitions:", sorted(STATES - {s for s, _ in T}))
print("do not reach CLOSED:", sorted(s for s in STATES if shortest_path(s, "CLOSED") is None))
print("\nCLOSED -> ESTABLISHED, shortest path:", shortest_path("CLOSED", "ESTABLISHED"))
print("avoiding SYN-SENT (passive side):",
shortest_path("CLOSED", "ESTABLISHED", forbidden={"SYN-SENT"}))
print("avoiding SYN-SENT and SYN-RCVD:",
shortest_path("CLOSED", "ESTABLISHED", forbidden={"SYN-SENT", "SYN-RCVD"}))
# Output:
# states: 11 - transitions: 21
# unreachable from CLOSED: []
# without outgoing transitions: []
# do not reach CLOSED: []
#
# CLOSED -> ESTABLISHED, shortest path: ['active OPEN / snd SYN', 'rcv SYN,ACK / snd ACK']
# avoiding SYN-SENT (passive side): ['passive OPEN', 'rcv SYN / snd SYN,ACK', 'rcv ACK of SYN']
# avoiding SYN-SENT and SYN-RCVD: None
The results hold for the diagram, not for all of TCP. Of the 11 states (21 transitions) all are reachable from CLOSED, none lacks exits and from every state there is a path that leads to CLOSED. The minimal paths to ESTABLISHED are two: the active side needs 2 events, the passive side 3. The last line is the safety property: if you remove both the SYN-SENT and SYN-RCVD states from the graph, ESTABLISHED is no longer reachable, that is in the diagram no connection is established without having exchanged the SYN segments.
What these checks can tell you and what they cannot
Reachability, absence of states without exits and properties of the type "X is never reached without passing through Y" are searches in a graph, and the program solves them in a few lines. "From every state there is a path to CLOSED" is instead a weaker property than it seems: it says that the exit is possible, not that it is inevitable. A system can have that path and go around in circles forever if the environment chooses it every time. For properties of the type "sooner or later it happens" you need fairness and temporal logic, the subject of the fourth article. And the number of states grows multiplicatively when several components run together (the product of two automata has as many states as there are pairs), a problem that the fifth article tackles with model checking.
Exercises
1. In the cart CANCELLED is flagged as a deadlock. Modify the program so that it is accepted as a terminal state and verify that the list of non-accepting deadlocks becomes empty.
Solution
It is enough to define F = {"COMPLETE", "CANCELLED"}. The states with no exits remain two, but both are in F and the expression (R - with_exits) - F gives the empty set.
2. How many states does the subset DFA have for "the 11th symbol from the end is a"?
Solution
2048, that is 211: the function nfa_from_suffix(11) passed to subsets gives 2048 states, and minimum confirms that they are all necessary.
Frequently asked questions
What is the difference between a DFA and an NFA?
In the DFA every (state, input) pair leads to a single state; in the NFA it can lead to several states, and the word is accepted if at least one path reaches an accepting state. They have the same expressive power, but converting an NFA into a DFA can make the states grow up to 2n, as the table shows.
Why can anbn not be recognized with a DFA?
Because a DFA has a finite number of states and cannot count a's beyond that number: reading enough a's, two different prefixes end in the same state, and the automaton can no longer distinguish how many a's it has read, hence how many b's it must expect. It is the content of the pumping lemma.
Mealy or Moore?
They are equivalent in power (a textbook theorem, here verified on an example): from the Mealy you get a Moore by taking as state the pair (state, output), as the program does. The Mealy usually has fewer states; the Moore has the output in the state and a small alignment difference (the initial output).
What you can do now
You can define an automaton with five components, simulate it and ask it questions of reachability, of absence of states without exits and of safety with a search in a graph. You can build the DFA of an NFA with the subset construction, check it against an independent reference and recognize when the explosion of states is unavoidable. You can use the pumping lemma to exclude a language from the regular ones and read a real state diagram, with the limit that its source declares. The next step is temporal logic, to express the properties over time that the graph alone does not tell.
This is the third article of the Formal Methods series. The previous one is Logic for specification: propositional and first-order; the next one is Temporal Logic: LTL and CTL.
The last article in the series, Petri Nets: structure, markings, reachability, liveness and safety, closes the path with a model that is an alternative to the state machine.
Sources
- RFC 9293, Transmission Control Protocol (TCP) - text downloaded and read: §3.3.2 (list and meaning of the eleven states), Figure 5 with the transitions and Notes 1-3 (RST not drawn; the diagram is only a summary); consulted on 2026-11-13
- Russ Cox, Regular Expression Matching Can Be Simple And Fast - page read: the
a?nancase with Perl over sixty seconds for 29 characters against twenty microseconds for the NFA simulation, and the historical note on Rabin and Scott (NFAs are simulated with DFAs whose states are sets of states); consulted on 2026-11-13 - Python documentation, re module - used as the independent reference for the programs (
re.fullmatch); the outputs reported are those of the programs run, not the text of the page; consulted on 2026-11-13
Cited through the article by Cox and verified only in the metadata on Crossref, without reading their text: M. O. Rabin and D. Scott, Finite Automata and Their Decision Problems, IBM Journal of Research and Development 3(2), 1959 (DOI 10.1147/rd.32.0114); K. Thompson, Regular expression search algorithm, Communications of the ACM 11(6), 1968 (DOI 10.1145/363347.363387). Programs run with Python 3.14.4 (python3 -I), twice each with identical output, except the timing one, which by nature changes from one run to another.
Article published 2026-10-08, graduate level.
Commenti
Caricamento commenti...
Sign in to comment