From Finite Automata to Regular Expressions and Back--A Summary on Descriptional Complexity

Hermann Gruber, Markus Holzer

The equivalence of finite automata and regular expressions dates back to the seminal paper of Kleene on events in nerve nets and finite automata from 1956. In the present paper we…