I came up with an algorithm to decide this language, but not sure if it is correct?

for every string w over {0,1} of length at most n1 x n2:
    if D1 accepts w and D2 rejects w:

Where n1 and n2 are the number of states in $D_1$ and $D_2$.

  • 2
    $\begingroup$ Have you tried proving that your algorithm works? This is how we know if an algorithm is correct or not. $\endgroup$ – Yuval Filmus Nov 8 '19 at 13:52
  • $\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$ – D.W. Nov 8 '19 at 19:20
  • $\begingroup$ Could you specify the alphabet of your language $L$? $\endgroup$ – J.-E. Pin Nov 10 '19 at 9:39

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.