# Which of the following regular expressions generate(s) no string with two consecutive 1’s?

This is a GRE practice question.

Which of the following regular expressions generate(s) no string with two consecutive 1’s? (Note that ε denotes the empty string.)

I. (1 + ε)(01 + 0)*

II. (01+10)*

III. (0+1)*(0+ε)

(A) I only

(B) II only

(C) III only

(D) I and II only

(E) II and III only

My understanding is that neither I nor III generates strings with 11. In I, a string containing 1 is either 1 or 1 surrounded by 0's. In III, all 1's are preceded by 0's. But the correct answer is A, so III must generate a string with 11 somehow. Please explain. Thanks!

• "In III, all 1's are preceded by 0's" are you sure? Try some examples of $(0+1)^*$ (what is the meaning of $(0+1)$?)
– Vor
Oct 15, 2012 at 7:36
• What is the meaning of plus? Usually it is one or more times, but then it is written in superscript. Is it just regular concatenation? No, must be or... Oct 15, 2012 at 11:37
• Isn't this a bit localized anyway? Oct 15, 2012 at 11:38
• It would be nice if the question could be put in more general terms.
– Raphael
Oct 16, 2012 at 7:21
• Thank you! I did confuse the meaning of +. I thought it was concatenation; it was union. I agree it's a pretty specific question. Oct 17, 2012 at 4:03

III is $(0+1)^* (0+ \epsilon)$ which means pick a word from $\Sigma^*$ where $\Sigma = \{0, 1 \}$ and then concatenate it with either $0$ or $\epsilon$.
so III Does generate a string with two consecutive $1$'s. In fact it generates every string which contains $1$'s, $0$'s or is empty.