Every Regular Language Has a Bipartite Cactus Automaton

Electronic Proceedings in Theoretical Computer Science, vol. 454, pp. 117–129

Abstract

Thompson's classical construction turns every regular expression into an equivalent ε-NFA whose transition graph is series-parallel.The construction uses ε-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 ε-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.

Authors 3

1. Mario Grobler

   University of Bremen

   Affiliation as printed

   University of Bremen

2. Till Koziel Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

3. Sebastian Siebertz

   University of Bremen

   Affiliation as printed

   University of Bremen