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.

  • $\begingroup$ 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". $\endgroup$ – C8H10N4O2 Mar 10 at 4:00
  • $\begingroup$ isn't the $L$ you got already a regular language? Whats wrong with how its defined? $\endgroup$ – 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.


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.