1
$\begingroup$

Assume a regular language contains all the strings that are ended with "01". We can draw the following DFA for it:

enter image description here

And I reversed the DFA according to this answer (designing a DFA and the reverse of it)

enter image description here

I expected this DFA to accept all strings that start with "10" but it is not. What is my mistake in drawing the reverse DFA?

$\endgroup$
3
  • $\begingroup$ Can you give a counter example? $\endgroup$
    – Yonatan N
    Nov 3 '18 at 21:58
  • 3
    $\begingroup$ The reverse "DFA" is a finite state automaton, but it is not deterministic. It does accept every string that starts with $10$ but you will have to select the proper path. So for example, for the string $100$ you do not follow the path from left to right (as you might expect) because you will get stuck. Instead you take the loop with $0$ in the middle state. $\endgroup$ Nov 4 '18 at 1:17
  • $\begingroup$ @HendrikJan You are right. The machine accepts all the string starting with "10"; you should just follow the correct path. $\endgroup$ Nov 4 '18 at 16:32
1
$\begingroup$

Answering my own question based on the comment by Hendrik Jan:

The reverse DFA is correct. It is just that it is not deterministic. It's an NFA, so we should follow all the paths possible. And if we do so, it will accept all the strings starting with "10".

Example: assume we want to test this string: "10001". and assume that states are named 1, 2, and 3 from the right. By following this path, the NFA accepts the input string: "1,2,2,2,3,3"

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