Regular set of the "does not contain" kind Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses
$L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$?
Well, the part that states that w must end with 00 is easy and I (think I) managed to find the regular set for it. But I can't modify it so that w won't contain 11.
I didn't find many articles about this subject on the internet, and the ones I did didn't help me much in this &quot;does not contain&quot; kind of problem. So it'd help a lot if you guys could mention some articles on regular sets to me.
If a string doesn't contain $11$, then any $1$ is followed by $0$, unless it is the final $1$ in the string. Therefore you can break the string up into pieces of the forms $0,10,1$, the last one appearing only at the very end. This leads to the following regular expression for the set of binary strings excluding $11$:
$$ (0+10)^*(\epsilon+1). $$
If we furthermore want the string to end with $0$, then we have no terminal $1$. On the other hand, we also want to disallow the empty string. Altogether, we get
$$ (0+10)^+. $$
A similar case analysis leads to a regular expression for your language. Details left to you.