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
