3
$\begingroup$

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)^*$?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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)^*. $$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thank you so much for your helpful $\endgroup$ – NoizyBoy Dec 7 '19 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 Dec 7 '19 at 23:39
  • $\begingroup$ Yes, but that wouldn’t fit the textual description. $\endgroup$ – Yuval Filmus Dec 8 '19 at 6:05

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.