Local elimination-strategies in automata for shorter regular expressions.
Stefan Gulan, Henning Fernau · 2008
Abstract. We propose a construction of regular expressions from particularly restricted NFA via extended automata. It proceeds in two main steps, elimination of cycles in the state graph followed by a recursive construction of the final regular expression. Inbetween these eliminations, series-parallel substructures are reduced to single transitions. The process gives rise to compact regular expressions by avoiding redundancies in the intermediate extended automata. Altough derived from state-elimination-techniques, the constructions are rather ’transitionoriented’. 1