0
$\begingroup$

If I want to find the reversal of a regular expression using an automata, Do I have to transform the automata to DFA if it wasn't ?

$\endgroup$
1
  • $\begingroup$ Colleague Vor has demonstrated that inverse (mirror image) of the language of a regular expression can be found by merely inverting the expression itself. So why would you use the automaton? $\endgroup$ Jul 26 at 19:45
0
$\begingroup$

No. Represent your automata as a directed graph where each edge is labelled as a symbol of the alphabet. Then:

  • Reverse all edges.
  • Change the former initial state to an non-initial accepting state.
  • Add a new initial state $q_0$, and add a transition (edge) $q_0 \overset{\varepsilon}{\to}q$ towards every state (vertex) $q$ that formerly was an accepting state.

This works even if the starting automata is a NFA.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.