# 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 "does not contain" kind of problem. So it'd help a lot if you guys could mention some articles on regular sets to me.

• Can you show what you have so far? If you want "does not contain 11", that means you can have zero or more of "0" or "01". – C8H10N4O2 Mar 10 at 4:00
• isn't the $L$ you got already a regular language? Whats wrong with how its defined? – nir shahar Mar 10 at 6:40

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.