Regular languages can use simpler cycle-based automata graphs

Every Regular Language Has a Bipartite Cactus Automaton

Formal Languages and Automata Theory

Summary

Regular languages can be represented using machines called automata. Earlier, these machines were known to have complex graph structures. The authors found that every regular language can be represented with a simpler kind of graph called a bipartite cactus, where cycles are well-structured and the graph has nice mathematical properties. This makes understanding and working with these machines easier in some ways. Their proof uses basic properties of these cactus graphs and works by breaking down the language step-by-step.

What this means in practice

  • For software engineers: Designing finite automata with simpler and well-structured transition graphs that are easier to analyze and optimize in compilers or pattern matching.
  • For network protocol developers: Creating protocol state machines with bounded complexity to ensure efficient implementation and verification.

A theory result. No direct application yet.

Authors

Mario Grobler, Till Koziel, Sebastian Siebertz

Abstract

Thompson's classical construction turns every regular expression into an equivalent epsilon-NFA whose transition graph is series-parallel. The construction uses epsilon-transitions, and eliminating them by the usual shortcut construction need not preserve planarity or the bound of two on the treewidth of the transition graph. Book and Chandra proved that every regular language nevertheless has an epsilon-free NFA with a planar transition graph. We show that the transition graph can in fact be chosen to be a bipartite cactus: every cycle is even, and any two cycles have at most one vertex in common. In particular, it is outerplanar and has treewidth at most two. This is a considerably more simple structure than the general series-parallel guarantee supplied by Thompson's construction. The proof is a direct induction on parity-typed regular expressions and uses only elementary closure properties of cactus graphs.