Official PYQ · 2014Set 2 · Q36Regular and Context-free LanguagesMCQ1 mark

GATE CS 2014 Set 2 Q36 — Regular and Context-free Languages

Let $L_1=\{w\in\{0,1\}^*\mid w$ $\text{ has at least as many occurrences of }$ $(110)'\text{s as }$ $(011)'\text{s} \}$ . Let $L_2=\{w \in\{0,1\}^*\ \mid w$ $\text{ has at least as many occurrences of }$ $(000)'\text{s as}$ $(111)'\text{s} \}$ . Which one of the following is TRUE?

View worked solution

Answer: A

To determine the regularity of $L_1$ and $L_2$ , we analyze the relationship between their respective substrings.

1. Analysis of $L_1$ :

The substrings are $110$ and $011$ . Notice that:

An occurrence of $110$ represents a transition from a block of $1$ s (of length $\ge 2$ ) to a $0$ .
An occurrence of $011$ represents a transition from a $0$ to a block of $1$ s (of length $\ge 2$ ).

Because these transitions must alternate, the number of occurrences of

110

and

011

in any string

w

can differ by at most

1

. That is,

|N(110) - N(011)| \le 1

. Since this difference is strictly bounded, a Finite Automaton can track it using a finite number of states. Thus, $L_1$ is regular.

2. Analysis of $L_2$ :

The substrings are $000$ and $111$ . Let us intersect $L_2$ with the regular language $R = 0^*1^*$ : $\text{For } a, b \ge 2, \quad L_2 \cap 0^*1^* = \{ 0^a 1^b \mid a \ge b \}$ This is a well-known non-regular language because it requires comparing two arbitrary independent counts. Since regular languages are closed under intersection, and $L_2 \cap R$ is non-regular, $L_2$ cannot be regular.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

Browse this topic

More Regular and Context-free Languages questions

GATE CS 2014 Set 2 Q36 — Regular and Context-free Languages

Related questions