The complexity of restricted regular expressions and the synthesis problem for finite automata

摘要

It is known that for every restricted regular expression of length n there exists a nondeterministic finite automaton with n + 1 states giving rise to the upper bound of 2n + 1 on the number of states of the corresponding reduced automaton. In this note we show that this bound can be attained for all n ⩾ 2, i.e., the upper bound 2n + 1 is optimal. An observation is then made about the synthesis problem for nondeterministic finite automata.