snippetModerate
Can we convert an NFA to a regular expression of polynomial length?
Viewed 0 times
expressioncannfapolynomialconvertlengthregular
Problem
Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$?
In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\mathcal{O}(n)$-state NFA.
In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\mathcal{O}(n)$-state NFA.
Solution
Using the concept of star height, Gruber and Holzer showed in Finite Automata, Digraph Connectivity, and Regular Expression Size that there exists a constant $C>1$ and a sequence of languages $L_n$ over $\{0,1\}$ which can be accepted by DFAs having $n$ states, but for which every regular expression has length at least $C^n$.
Context
StackExchange Computer Science Q#84011, answer score: 11
Revisions (0)
No revisions yet.