An Optimal Construction of Finite Automata from Regular Expressions
Stefan Gulan, Henning Fernau · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2008
We consider the construction of finite automata from their corresponding regular expressions by a series of digraph-transformations along the expression\'s structure. Each intermediate graph represents an extended finite automaton accepting the same language. The character of our construction allows a fine-grained analysis of the emerging automaton\'s size, eventually leading to an optimality result.