GATE CSE 1996 | Question: 1.10

Question

Let $L \subseteq \Sigma^*$ where $\Sigma = \left\{a,b \right\}$. Which of the following is true?

1. $L = \left\{x \mid x \text{ has an equal number of } a\text{'s and }b\text{'s}\right \}$ is regular
2. $L = \left\{a^nb^n \mid n \geq 1\right \}$ is regular
3. $L = \left\{x \mid x \text{ has more number of }a\text{'s than }b\text{'s}\right \}$ is regular
4. $L = \left\{a^mb^n \mid m \geq 1, n \geq 1 \right \}$ is regular

Comments

EQUAL number of a's followed by equal number of b's is well known CFL

ANY number of a's followed by any number of b's is REGULAR , we can easily write R.E or draw a DFA accepting this L

R.E over Σ = {a.b} is a*b* or a+b+

---

regex of $D)$ : $a^+b^+$, since there exists regex of $L$, $L$ is regular

---

This may help : https://youtu.be/UDfDswTv0Ic?list=PLIPZ2_p3RNHhXeEdbXsi34ePvUjL8I-Q9&t=8836

Answer 1

Correct Option: D

Since $n$ and $m$ are independent finite memory suffices.

Options (a) and (b) are the same. They and option (c) require keeping track of the counts of $a’s$ which cannot be done using a finite automata but can be done using a DPDA and hence are not regular but DCFL.

Comments

I think option A and B are not the same. Option A states that there are equal number of a's and b's.

Option B states that  a and b should be in order and they should have same count.

ex. aabbaabb will not be in option B

---

It doesn't genarate aaabbb. we need stack here to do this. regx is not possible to write for this language.

---

Option A and B they have this type of relation opt b is subset of opt a. a has more strings than b.

for eg: option a can generate aabaabbb which is not possible in option B.

Answer 2

• in option a,b,c  there is one compatision between a and b . which is done bt pda. so it is CFL but not regular.

 

• in option d we can write a regulag expression (aa*bb*) . so it is regular

Comments

or more easily we can write (a+b+) as regex.

Answer 3

In all the options we have seen that there exist a comparison between the powers of 'a' and 'b' hence they can't be regular. In option D number of a's are independent of number of b's hence it is regular.

(D)

Answer 4

Option (a)

$$
L_a = { x \in {a,b}^* \mid \#_a(x) = \#_b(x) }
$$
(i.e., all strings with an equal number of $a$'s and $b$'s, in any order).

Claim: $L_a$ is not regular.

Proof (Pumping Lemma):
Assume $L_a$ is regular. Then there exists a pumping length $p \geq 1$. Consider the string
$$
w = a^p b^p.
$$
Clearly, $w \in L_a$ since it contains $p$ $a$'s and $p$ $b$'s, and $|w| = 2p \geq p$.

By the Pumping Lemma, $w = xyz$ with

1. $|xy| \leq p$,

2. $|y| \geq 1$,

3. $xy^i z \in L_a$ for all $i \geq 0$.

Since the first $p$ symbols of $w$ are all $a$'s, condition (1) implies $y = a^k$ for some $1 \leq k \leq p$.

Now consider $i = 0$:
$$
xy^0z = a^{p - k} b^p.
$$
This string has $p - k$ $a$'s and $p$ $b$'s, so $\#_a \ne \#_b$, and thus $xy^0z \notin L_a$, contradicting the Pumping Lemma.

Hence, $L_a$ is not regular.

Remark: Although $L_a$ includes strings like abab or baab, the Pumping Lemma only requires one string in the language of sufficient length to derive a contradiction. The choice $a^p b^p \in L_a$ is valid and sufficient.

PDA for same:

---

Option (b)

$$
L_b = { a^n b^n \mid n \geq 1 }
$$

Claim: $L_b$ is not regular.

Proof (Pumping Lemma):
Assume $L_b$ is regular. Let $p$ be the pumping length and choose $w = a^p b^p \in L_b$. As before, $w = xyz$ with $|xy| \leq p$, so $y = a^k$, $k \geq 1$.

Then $xy^0z = a^{p - k} b^p \notin L_b$, violating the Pumping Lemma.

Hence, $L_b$ is not regular.

PDA for same:

---

Option (c)

$$
L_c = { x \in {a,b}^* \mid \#_a(x) > \#_b(x) }
$$

Claim: $L_c$ is not regular.

Proof (Myhill–Nerode):
Consider again $S = { a^n \mid n \geq 0 }$. For $i < j$, let $z = b^i$. Then:

• $a^i z = a^i b^i \notin L_c$ (equal counts),

• $a^j z = a^j b^i \in L_c$ (since $j > i$).

Thus, $a^i$ and $a^j$ are distinguishable. Infinitely many equivalence classes ⇒ $L_c$ is not regular.

---

Option (d)

$$
L_d = { a^m b^n \mid m \geq 1,\ n \geq 1 }
$$

Claim: $L_d$ is regular.

Proof (Regular Expression):
Every string in $L_d$ consists of one or more $a$'s followed by one or more $b$'s, with no interleaving. This is exactly described by the regular expression. $a^+b^+$
Since a regular expression exists, $L_d$ is regular.

Alternative (Myhill–Nerode):
The language can be recognized by a DFA with the following states:
$q_0$: start (no input),
$q_1$: seen at least one $a$, no $b$ yet,
$q_2$: seen at least one $a$ followed by at least one $b$ (accepting),
$q_3$: seen a $b$ before any $a$, or seen $ba$ (dead/rejecting state).

Only finitely many states are needed, so the Myhill–Nerode relation has finitely many equivalence classes. Hence, $L_d$ is regular.

---

 

Among the four options, only Option (d) defines a regular language. Options (a), (b), and (c) all require unbounded comparison or counting of symbol frequencies, which cannot be achieved by any finite automaton.

$$
\boxed{\text{d. } L = {a^m b^n \mid m \geq 1,\ n \geq 1} \text{ is regular}}
$$

Answer 5

Let us analyse all the options:

option A: x has equal number of a's and  b's

for this kind of string generation, we need to maintain a stack where we will pop each a when we encounter  b.

So for maintaining stack we need Push down automata where we can push a for every "a" we encounter and pop a for every "b" we encounter. 

Also, every PDA generates Context Free Language, So option A is not regular.

Option B: We will build a push down automata where we encounter 'a', we will stay in same state/push a to the stack and when we encounter the first b, we willmove to next state and pop the a simultaneously, to check if number of b's after all a's have occured is same or not.

So, again option B is CFL and not regular.

Optionc C: Here we have a similar implementation like option a and b but , here we should have a's left in the stack after whole string has been parsed.

Again this is CFL and not regular.

Option D: we can observe that there is no relation as well as comparison between m and n. so this can be interpreted as a*b* pattern, which is regular.

Option D is Regular.