0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Don't you think all DFAs that accept $(101)^*$ have something in common? $\endgroup$ Commented Nov 29, 2016 at 4:22
  • $\begingroup$ You could hardwire a DFA for $(101)^*$ into your program, but your solution is also correct. $\endgroup$ Commented Nov 29, 2016 at 6:34
  • 1
    $\begingroup$ We generally don't grade answers here. We prefer to help you with concrete problems rather than suspicions. $\endgroup$ Commented Nov 29, 2016 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$ Commented Nov 29, 2016 at 8:23

0