How to convert NFA to Regular Expression

regex formal-languages nfa
formatjam picture formatjam · Feb 9, 2012 · Viewed 13.7k times · Source

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

Answer

buzypi picture buzypi · Feb 9, 2012

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]

Related questions

Regular expression to match a line that doesn't contain a word

I know it's possible to match a word and then reverse the matches using other tools (e.g. grep -v). However, is it possible to match lines that do not contain a specific word, e.g. hede, using a regular …

Read More
How to validate an email address in JavaScript

Is there a regular expression to validate an email address in JavaScript?

Read More
RegEx match open tags except XHTML self-contained tags

I need to match all of these opening tags: <p> <a href="foo"> But not these: <br /> <hr class="foo" /> I came up with this and wanted to make sure I've got …

Read More