Question

Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

• A. $0^{\ast }(10+1{)}^{\ast }$
• B. $0^{\ast }{1010}^{\ast }$
• C. $0^{\ast }{1}^{\ast }{01}^{\ast }$
• D. $0^{\ast }(1+0{)}^{\ast }$

Answer 1

The correct option is A $0^{\ast }(10+1{)}^{\ast }$

(a) r.e. (regular expression) = $0^{\ast }(1+0{)}^{\ast }$ can generate string 100, which contains substring 100

(b) r.e. (regular expression) = $0^{\ast }{1010}^{\ast }$ can generate string 10100, which contain 100 as a substring. Also, this regular expression cannot generate $ϵ$ which is in the given language.

(c) r.e. (regular expression) = $0^{\ast }{1}^{\ast }{01}^{\ast }$ generates strings which doesn't contain 100 as substring. However, $ϵ$ is the smallest string which doesn't contain 100 as substring but above RE cant generate $ϵ$.

(d) r.e (regular expression) = $0^{\ast }(10+1{)}^{\ast }$ generates all strings which doesn't contain 100 as substring.