Podemos converter um NFA em uma expressão regular de comprimento polinomial?

Podemos converter um NFA com estados em uma expressão regular de length ?$n$$\mathrm{poly}(n)$

Por outro lado, é sabido que uma expressão regular de comprimento pode ser facilmente convertida em um NFA do estado .$n$$\mathcal{O}(n)$

Usando o conceito de altura de estrela, Gruber e Holzer mostraram em autômatos finitos, conectividade Digraph e tamanho de expressão regular que existe uma constante e uma sequência de idiomas sobre que podem ser aceitos pelos DFAs tendo estados, mas para os quais toda expressão regular tem comprimento pelo menos .$C>1$$L_n$$\{0,1\}$$n$$C^n$