Given a minimal NFA for a finite language, is there a polynomial-time algorithm to find a minimal regular expression for the same language?

This question is based on a recent question regarding minimization of regular expressions for finite languages given a regular expression. I was surprised to learn there don't appear to be any stronger results. (see Is there a polynomial-time algorithm to minimize regular expressions without Kleene closures/stars?)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.