# Is L={0,1}* without strings that start with 00 decidable?

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

## 1 Answer

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

• Er... That regular expression doesn't match the language you're asking about. It's close, but it's wrong. – David Richerby Feb 19 '18 at 23:11
• what is the correct one then? – crystyxn Feb 20 '18 at 0:39
• You're looking for strings that start with two zeroes, which isn't what your regular expression starts with. – David Richerby Feb 20 '18 at 0:48
• 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