There is a theorem that says if a language is regular, its reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?

  • $\begingroup$ I'm assuming by reverse, you mean its complement. Just change every accepting state in a DFA to rejecting, and every rejecting to accepting. $\endgroup$ – Daniil Agashiyev Feb 21 '15 at 17:02
  • $\begingroup$ What do you mean by a DFA which does all the things itself? $\endgroup$ – babou Feb 22 '15 at 10:49

$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:

  1. Reverse all edges in the transition diagram.
  2. The accepting state for the LR automaton is the start state for the main automaton.
  3. Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.
  4. Convert this NFA back into a DFA.

To write the reverse of a DFA, Change all the initial states to final and the final ones to initials(for the later, if there are multiple final states, use a new state and use null transitions to each of them). At last... Reverse the edges.

  • 2
    $\begingroup$ There's a catch to reversing the edges at least mentioned in the accepted answer. Speaking of which: Does your answer add anything to it? $\endgroup$ – greybeard Feb 13 '20 at 21:22

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.