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$
$\endgroup$
2
-
$\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 AgashiyevFeb 21, 2015 at 17:02
-
$\begingroup$ What do you mean by a DFA which does all the things itself? $\endgroup$– babouFeb 22, 2015 at 10:49
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:
- Reverse all edges in the transition diagram.
- The accepting state for the LR automaton is the start state for the main automaton.
- Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.
- Convert this NFA back into a DFA.
$\begingroup$
$\endgroup$
1
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$ Feb 13, 2020 at 21:22