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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you give a counter example? $\endgroup$
    – Yonatan N
    Commented Nov 3, 2018 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$
    – Hendrik Jan
    Commented Nov 4, 2018 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$
    – Hamid Mohammadi
    Commented Nov 4, 2018 at 16:32

1 Answer 1

Reset to default
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"

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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