I tried to prove that the language A = {w | w contains twice as many 0s as 1s} is decidable.

My current solution goes as follows:

We "construct" a TM M deciding A in the following way:

For the input string w M does the following:

I) Scan the tape from left to right and mark the first unmarked 1 that is found. If none is found go to IV). Otherwise move the head back to the start of the tape.

II) Scan the tape from left to right and mark the first two unmarked 0s that are found. If none are found reject w.

III) Move the head back to the start of the tape and do I).

IV) Scan the tape for any remaining 0s. If none are found accept w, otherwise reject w.

Is this correct? Any form of feedback would be welcome.

Thanks in advance.


closed as unclear what you're asking by fade2black, Yuval Filmus, Evil, David Richerby, Juho Sep 18 '17 at 8:34

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ "Check my homework" type of questions are not a good fit for this site, as the answers are not very interesting. $\endgroup$ – adrianN Sep 14 '17 at 13:00
  • 1
    $\begingroup$ Hint: Show that the language is context-free. $\endgroup$ – Raphael Sep 14 '17 at 14:11
  • 2
    $\begingroup$ Hint: Since anything you can do on a computer can be done with a TM, could you write a program to recognize this language? $\endgroup$ – Rick Decker Sep 14 '17 at 16:08

Browse other questions tagged or ask your own question.