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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Don't you think all DFAs that accept $(101)^*$ have something in common? $\endgroup$
    – André Souza Lemos
    Nov 29, 2016 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, 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$
    – Yuval Filmus
    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$
    – David Richerby
    Nov 29, 2016 at 8:23

0

Reset to default