HiveBrain v1.2.0
Get Started
← Back to all entries
snippetModerate

Can we convert an NFA to a regular expression of polynomial length?

Submitted by: @import:stackexchange-cs··
0
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.

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.