Let \(L_1 = \{ w \in \{0,1\}^* | w\) has at least as many occurrences of…

GATE · 2014 · CS · Set 2 · Computer Science & IT

Let L1={w∈{0,1}∗∣wL_1 = \{ w \in \{0,1\}^* | w has at least as many occurrences of (110)’s as (011)’s}. Let L2={w∈{0,1}∗∣wL_2 = \{ w \in \{0,1\}^* | w has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?

  1. A.

    L1L_1 is regular but not L2L_2

  2. B.

    L2L_2 is regular but not L1L_1

  3. C.

    Both L1L_1 and L2L_2 are regular

  4. D.

    Neither L1L_1 nor L2L_2 are regular

Attempted by 272 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…