Can we convert an NFA to a regular expression of polynomial length?
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&gt;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$.