Menu
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
241
In computer science, Thompson's construction algorithm, also called the McNaughton–Yamada–Thompson algorithm, is a method of transforming a regular expression into an equivalent nondeterministic finite automaton (NFA). This NFA can be used to match strings against the regular expression.
To convert the regular expression (RE) to Finite Automata (FA), we can use the Subset method. Subset method is used to obtain FA from the given RE. Step 1 − Construct a Transition diagram for a given RE by using Non-deterministic finite automata (NFA) with ε moves.
Utility – To construct DFA from a given regular expression, we can first construct an NFA for the given expression and then convert this NFA to DFA by a subset construction method. But to avoid this two-step procedure, the other way round is to directly construct a DFA for the given expression.
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]
69
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
