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)^*$?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
3
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)^*. $$
answered Dec 7 '19 at 12:13
-
-
$\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
