Glushkov automaton in Python
Builds an epsilon-free NFA with one state per symbol occurrence plus one initial state.
- File
glushkov_automaton.py, 104 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/glushkov-automaton/. The authors are listed in prov/0FZKDT.jsonl.
"""The Glushkov (position) automaton of a regular expression.
A regular expression is a tuple:
("empty",) for the empty language, ("eps",) for the empty string,
("sym", a) for one symbol, ("alt", r, s), ("cat", r, s) and ("star", r).
"""
from __future__ import annotations
from dataclasses import dataclass
from typing import Any
Regex = tuple[Any, ...]
@dataclass
class Glushkov:
"""States 0..k. State 0 is initial; state p >= 1 is the p-th symbol occurrence.
symbol[p] is the symbol of position p (symbol[0] is unused), succ[0] is
First, succ[p] is Follow(p), and every move into q reads symbol[q].
"""
symbol: list[str]
succ: list[list[int]]
accepting: set[int]
def transitions(self) -> list[tuple[int, str, int]]:
"""All moves (p, a, q) of the automaton, sorted."""
return sorted((p, self.symbol[q], q) for p in range(len(self.succ)) for q in self.succ[p])
def glushkov(regex: Regex) -> Glushkov:
"""Build the Glushkov automaton of `regex`, with k + 1 states for k symbol occurrences.
The tree is walked in postorder with an explicit stack, so deep
expressions need no recursion. Cost: O(m * k^2) time and O(m * k) space
for m nodes, without the star normal form refinement.
"""
symbol = [""]
follow: list[set[int]] = [set()]
# Each finished node leaves (nullable, first, last) on this stack.
done: list[tuple[bool, set[int], set[int]]] = []
todo: list[tuple[Regex, bool]] = [(regex, False)]
while todo: # @line L2
node, ready = todo.pop()
tag = node[0]
if not ready and tag in ("alt", "cat", "star"):
todo.append((node, True))
for child in reversed(node[1:]):
todo.append((child, False))
continue
if tag == "empty": # @line L3
done.append((False, set(), set()))
elif tag == "eps": # @line L4
done.append((True, set(), set()))
elif tag == "sym": # @line L5
symbol.append(node[1]) # @line L1
follow.append(set())
p = len(symbol) - 1
done.append((False, {p}, {p}))
elif tag == "alt": # @line L6
n2, f2, l2 = done.pop()
n1, f1, l1 = done.pop()
done.append((n1 or n2, f1 | f2, l1 | l2))
elif tag == "cat": # @line L7
n2, f2, l2 = done.pop()
n1, f1, l1 = done.pop()
for p in l1: # @line L8
follow[p] |= f2
nullable = n1 and n2 # @line L9
first = f1 | f2 if n1 else f1 # @line L10
last = l1 | l2 if n2 else l2 # @line L11
done.append((nullable, first, last))
elif tag == "star": # @line L12
n1, f1, l1 = done.pop()
for p in l1: # @line L13
follow[p] |= f1
done.append((True, f1, l1)) # @line L14
else:
raise ValueError(f"unknown node {node!r}")
nullable, first, last = done.pop()
follow[0] = first # @line L15
succ = [sorted(f) for f in follow] # @line L16
accepting = set(last) # @line L17
if nullable:
accepting.add(0)
return Glushkov(symbol, succ, accepting) # @line L18
def accepts(g: Glushkov, word: str) -> bool:
"""Run the automaton on `word` with a set of current states.
Cost: O(len(word) * number of moves) time, O(k) space.
"""
current = {0}
for c in word:
current = {q for p in current for q in g.succ[p] if g.symbol[q] == c}
if not current:
return False
return bool(current & g.accepting)
test_glushkov_automaton.py 212 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/glushkov-automaton/. The authors are listed in prov/0FZKDT.jsonl.
import itertools
import random
from glushkov_automaton import accepts, glushkov
EMPTY = ("empty",)
EPS = ("eps",)
def parse(text):
"""Parse | , concatenation, *, parentheses, ε and ∅ into the tuple form."""
pos = 0
def peek():
return text[pos] if pos < len(text) else None
def p_alt():
nonlocal pos
r = p_cat()
while peek() == "|":
pos += 1
r = ("alt", r, p_cat())
return r
def p_cat():
items = []
while peek() is not None and peek() not in "|)":
items.append(p_rep())
if not items:
return EPS
r = items[0]
for x in items[1:]:
r = ("cat", r, x)
return r
def p_rep():
nonlocal pos
r = p_atom()
while peek() == "*":
pos += 1
r = ("star", r)
return r
def p_atom():
nonlocal pos
c = peek()
pos += 1
if c == "(":
r = p_alt()
assert peek() == ")"
pos += 1
return r
if c == "ε":
return EPS
if c == "∅":
return EMPTY
return ("sym", c)
r = p_alt()
assert pos == len(text)
return r
def language(r, bound):
"""All strings of L(r) of length at most bound, by enumeration."""
t = r[0]
if t == "empty":
return set()
if t == "eps":
return {""}
if t == "sym":
return {r[1]} if bound >= 1 else set()
if t == "alt":
return language(r[1], bound) | language(r[2], bound)
if t == "cat":
a, b = language(r[1], bound), language(r[2], bound)
return {x + y for x in a for y in b if len(x) + len(y) <= bound}
body = language(r[1], bound) - {""}
result, frontier = {""}, {""}
while frontier:
frontier = {x + y for x in frontier for y in body if len(x) + len(y) <= bound} - result
result |= frontier
return result
def words(alphabet, bound):
for k in range(bound + 1):
for t in itertools.product(alphabet, repeat=k):
yield "".join(t)
def random_regex(rng, alphabet, depth):
if depth == 0 or rng.random() < 0.25:
x = rng.random()
if x < 0.08:
return EMPTY
if x < 0.18:
return EPS
return ("sym", rng.choice(alphabet))
k = rng.random()
if k < 0.35:
return ("alt", random_regex(rng, alphabet, depth - 1), random_regex(rng, alphabet, depth - 1))
if k < 0.75:
return ("cat", random_regex(rng, alphabet, depth - 1), random_regex(rng, alphabet, depth - 1))
return ("star", random_regex(rng, alphabet, depth - 1))
def count_symbols(r):
stack, k = [r], 0
while stack:
x = stack.pop()
if x[0] == "sym":
k += 1
elif x[0] in ("alt", "cat", "star"):
stack.extend(x[1:])
return k
def is_deterministic(g):
return all(len({g.symbol[q] for q in s}) == len(s) for s in g.succ)
def test_example_page():
g = glushkov(parse("(a|b)*ab"))
assert g.symbol == ["", "a", "b", "a", "b"]
assert g.succ == [[1, 2, 3], [1, 2, 3], [1, 2, 3], [4], []]
assert g.accepting == {4}
assert len(g.transitions()) == 10
current, seen = {0}, []
for c in "abab":
current = {q for p in current for q in g.succ[p] if g.symbol[q] == c}
seen.append(sorted(current))
assert seen == [[1, 3], [2, 4], [1, 3], [2, 4]]
assert accepts(g, "abab")
assert not accepts(g, "aba")
def test_example_determinism():
g1 = glushkov(parse("(a|b)*a"))
g2 = glushkov(parse("b*a(b*a)*"))
assert not is_deterministic(g1)
assert is_deterministic(g2)
assert g2.succ == [[1, 2], [1, 2], [3, 4], [3, 4], [3, 4]]
for w in words("ab", 8):
assert accepts(g1, w) == accepts(g2, w) == w.endswith("a")
def test_example_star_normal_form():
g = glushkov(parse("(a*b*)*"))
assert g.succ == [[1, 2], [1, 2], [1, 2]]
assert g.accepting == {0, 1, 2}
h = glushkov(parse("(a|b)*"))
assert g.transitions() == h.transitions()
def test_edge_cases():
for text, yes, no in [
("∅", [], ["", "a"]),
("ε", [""], ["a"]),
("∅*", [""], ["a"]),
("ε*", [""], ["b"]),
("((a*)*)*", ["", "aaaa"], ["ab"]),
("(ε|∅)*a", ["a"], ["", "aa"]),
("a∅|∅", [], ["a", ""]),
]:
g = glushkov(parse(text))
assert all(accepts(g, w) for w in yes)
assert not any(accepts(g, w) for w in no)
assert glushkov(parse("∅")).succ == [[]]
assert glushkov(parse("ε")).accepting == {0}
def test_deep_expression_without_recursion():
deep = ("sym", "a")
for _ in range(5000):
deep = ("cat", EPS, deep)
g = glushkov(deep)
assert len(g.symbol) == 2
assert accepts(g, "a") and not accepts(g, "")
long = ("star", ("alt", ("sym", "a"), ("sym", "b")))
assert accepts(glushkov(long), "ab" * 20000)
def test_random_against_enumeration():
rng = random.Random(20261106)
for trial in range(900):
alphabet = "ab" if trial % 2 else "abc"
bound = 6 if alphabet == "ab" else 4
r = random_regex(rng, alphabet, rng.randint(0, 5))
g = glushkov(r)
k = count_symbols(r)
assert len(g.symbol) == len(g.succ) == k + 1
assert len(g.transitions()) <= k * k + k
assert all(0 not in s for s in g.succ)
expected = language(r, bound)
for w in words(alphabet, bound):
assert accepts(g, w) == (w in expected)
def test_random_nested_stars():
rng = random.Random(7)
for _ in range(300):
r = random_regex(rng, "ab", 3)
for _ in range(rng.randint(1, 3)):
r = ("star", ("alt", r, EPS)) if rng.random() < 0.5 else ("star", r)
g = glushkov(r)
expected = language(r, 6)
for w in words("ab", 6):
assert accepts(g, w) == (w in expected)
What the next level needs
- the tests did not run in this build