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.

• 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. – Yuval Filmus Feb 19 '18 at 22:22

so turns out its decidable because its the regular expression $L = 01(0|1)$*
• 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} ! – crystyxn Feb 20 '18 at 0:52
• But this is the language of strings that do begin with $01$, not the ones that don't. – David Richerby Dec 12 '18 at 10:26