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!

  • 4
    $\begingroup$ "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)$?) $\endgroup$
    – Vor
    Commented Oct 15, 2012 at 7:36
  • 2
    $\begingroup$ 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... $\endgroup$ Commented Oct 15, 2012 at 11:37
  • 2
    $\begingroup$ Isn't this a bit localized anyway? $\endgroup$ Commented Oct 15, 2012 at 11:38
  • 1
    $\begingroup$ It would be nice if the question could be put in more general terms. $\endgroup$
    – Raphael
    Commented Oct 16, 2012 at 7:21
  • $\begingroup$ Thank you! I did confuse the meaning of +. I thought it was concatenation; it was union. I agree it's a pretty specific question. $\endgroup$ Commented Oct 17, 2012 at 4:03

2 Answers 2


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.


A is correct only. In II:0110 string present which has two consecutive 11 In III also 11 contain from (0+1)* expression...

  • $\begingroup$ I don't see what this adds over the other answer, which makes the same point more clearly. $\endgroup$
    – Raphael
    Commented Aug 3, 2016 at 13:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.