5
$\begingroup$

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

$\endgroup$
  • $\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
9
$\begingroup$

$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.
$\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.