Which one of the following regular expressions is NOT equivalent to the…

2004

Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?

  1. A.

    (a* + b* + c*)*

  2. B.

    (a*b*c*)*

  3. C.

    ((ab)* + c*)*

  4. D.

    (a*b* + c*)*

Attempted by 30 students.

Show answer & explanation

Correct answer: C

The regular expression (a + b + c)* matches any string composed of a, b, and c in any order and repetition. Option A (a* + b* + c*)* is equivalent because it allows any combination of a, b, and c in arbitrary order. Option B (a*b*c*)* is also equivalent as it allows any sequence of a, b, and c in blocks. Option D (a*b* + c*)* allows sequences of a's followed by b's or just c's, which is still equivalent. However, Option C ((ab)* + c*)* only allows strings where ab appears in pairs or c's appear alone, missing valid combinations like 'ba' or 'ac'. Thus, C is not equivalent.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir