Let L be the set of all strings over the alphabet {a, b}, including the empty string ε, that do not contain bb as a substring. Which one of the following regular expressions denotes exactly L?

Question

Accepted Answer

(A) (a + ba)^*(ε + b). Method: describe the structure of the language, then test each option on short witnesses. In a string with no bb, every b is followed by an a unless it is the last symbol. So the string is a sequence of blocks a or ba, optionally followed by one final b: (a + ba)^*(ε + b). Conversely, gluing such blocks never puts two bs together, because each ba block ends in a. Test the others with one string…

Answer

(a + ba)^*

Answer

(a + ab)^*(ε + b)

Answer

(ε + b)(a + ba)^*

Option	Witness	Why it fails
(b)	$b$	in $L$ , but every string of (b) is empty or ends in $a$
(c)	$abb$	generated as $ab \cdot b$ , but contains $bb$
(d)	$bba$	generated as $b \cdot ba$ , but contains $bb$

Regular expressions and regular languages: GATE CS question with solution

Solution MCQ · 1 mark · −⅓ if wrong