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

Problem Detail: 

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!

Asked By : Tootsie Rolls

Answered By : Sam Jones

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6086