Question

The set of all strings over ∑ = {a,b} in which all strings having bbbb as substring is?

(a) (a+b)* bbbb (a+b)*

(b) (a+b)* bb (a+b)*bb

(c) bbb(a+b)*

(d) bb (a+b)*

This question was posed to me in class test.

This interesting question is from Obtaining the regular Expression from the Finite automata in chapter Finite Automata and Regular Expression of Compiler

Answer 1

The correct option is (a) (a+b)* bbbb (a+b)*

To explain: Out of  all RE mentioned only the first string  certainly has bbbb as substring. Rest all just have a possibility of having it.