How can I construct a regular expression for the language over $\{0,1\}$ which is the complement of the language represented by the regular expression $10(0+1)^*$?


1 Answer 1


If a word doesn't start with $10$, then either it starts with some other combination of two letters, or it is shorter than two letters. All in all, we get the following regular expression for your language: $$ \epsilon + 0 + 1 + (00+01+11)(0+1)^*. $$

  • $\begingroup$ thank you so much for your helpful $\endgroup$
    – NoizyBoy
    Commented Dec 7, 2019 at 13:06
  • $\begingroup$ I must admit I'm not very familiar with this style of regular expressions, but couldn't you say e+1+(0+11)(0+1)*? $\endgroup$
    – CJ Dennis
    Commented Dec 7, 2019 at 23:39
  • $\begingroup$ Yes, but that wouldn’t fit the textual description. $\endgroup$ Commented Dec 8, 2019 at 6:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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