The string 1101 does not belong to the set represented by

1998

The string 1101 does not belong to the set represented by

  1. A.

    110*(0 + 1)

  2. B.

    1(0 + 1)*101

  3. C.

    (10)*(01)*(00 + 11)*

  4. D.

    (00 + (11)*01)*

Attempted by 21 students.

Show answer & explanation

Correct answer: C

Check whether 1101 can be generated by each regular expression. In option A, choose one 0 from 0* and then choose 1 from (0 + 1), so 110*(0 + 1) generates 1101. In option B, choose the middle (0 + 1)* part as empty, so 1(0 + 1)*101 generates 1101. In option C, the expression first allows only 10 blocks, then 01 blocks, then 00 or 11 blocks. The string 1101 cannot be decomposed in that required order, so it is not generated. In option D, choose one repetition of 11 inside (11)* and then 01, so the inner block generates 1101. Therefore, 1101 does not belong only to option C.

Explore the full course: Gate Guidance By Sanchit Sir