Which of the following are regular sets?

2008

Which of the following are regular sets?

  1. A.

    {anb2m|n≥0, m≥0}

  2. B.

    {anbm | n = 2m}

  3. C.

     {anbm n≠m}

  4. D.

     {xcy | x,y ∈ {a,b}*}

Attempted by 15 students.

Show answer & explanation

Correct answer: A, D

Option A, {an b2m} | n≥0, m≥0}, is regular because it represents strings with any number of a's followed by an even number of b's, which can be recognized by a finite automaton. Option D, {xcy | x,y ∈ {a,b}*}, is regular as it describes strings containing exactly one 'c' surrounded by any combination of a's and b's, which is also regular. Options B and C involve conditions (n=2m and n≠m) that require counting, making them non-regular. Thus, only A and D are regular sets.

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

Explore the full course: Gate Guidance By Sanchit Sir