regexformal-languagesnfa

How to convert NFA to Regular Expression

I knew that converting a regular expression to a NFA, there is a algorithm.

But I was wondering if there is a algorithm to convert a NFA to regular expression. If there is, what is it?

And if there isn't, I am also wondering if all NFA can convert to a regular expression. Is there a NFA that a regular expression that cannot represent?

Thank you! :D

Solution

  • Here is an algorithm where each transition is incrementally replaced with a regex, until there is only an initial and final state: https://courses.engr.illinois.edu/cs373/sp2009/lectures/lect_08.pdf [PDF]