I want to prove that $L = \{\langle T\rangle\mid T \text{ is a DFA and $L(T)$=$(101)^*$}\}$ is decidable.

I have the following idea in mind:

I design a TM $M$ such that, first of all, $M$ converts $(101)^*$ to NFA $P$. Then it converts $P$ to DFA $K$. After that $M$ determines whether $K$ and $T$ recognise the same language using the fact that $EQ = \{\langle A,B\rangle\mid A,B \text{ are DFAs and $L(A)=L(B)$}\}$ is decidable.

Is the solution idea correct? If not, then what would be the best way to solve the problem?

  • $\begingroup$ Don't you think all DFAs that accept $(101)^*$ have something in common? $\endgroup$ – André Souza Lemos Nov 29 '16 at 4:22
  • $\begingroup$ You could hardwire a DFA for $(101)^*$ into your program, but your solution is also correct. $\endgroup$ – Yuval Filmus Nov 29 '16 at 6:34
  • 1
    $\begingroup$ We generally don't grade answers here. We prefer to help you with concrete problems rather than suspicions. $\endgroup$ – Yuval Filmus Nov 29 '16 at 6:35
  • 3
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Nov 29 '16 at 8:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.