Say you have a language L = "{0,1}* without strings that start with 00". How do you prove this is decidable? I'm drawing a blank on this one.

  • 1
    $\begingroup$ Your language is regular, and so decidable. You can convert a DFA accepting this language to a Turing machine accepting it, if you so desire. $\endgroup$ – Yuval Filmus Feb 19 '18 at 22:22

so turns out its decidable because its the regular expression $L = 01(0|1)$*

  • $\begingroup$ Er... That regular expression doesn't match the language you're asking about. It's close, but it's wrong. $\endgroup$ – David Richerby Feb 19 '18 at 23:11
  • $\begingroup$ what is the correct one then? $\endgroup$ – crystyxn Feb 20 '18 at 0:39
  • $\begingroup$ You're looking for strings that start with two zeroes, which isn't what your regular expression starts with. $\endgroup$ – David Richerby Feb 20 '18 at 0:48
  • $\begingroup$ it seems that I was wrong in the original post about the description! it should be that L accepts any string that starts with 01 over the alphabet {0,1} ! $\endgroup$ – crystyxn Feb 20 '18 at 0:52
  • $\begingroup$ But this is the language of strings that do begin with $01$, not the ones that don't. $\endgroup$ – David Richerby Dec 12 '18 at 10:26

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.