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

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

 shefali1 

how u accept string "bbaa" using ur regular expression which is accepted by option A

---

I think there is little difference between option A) and option B). In option B, it is must that string should always start with 'a' and end with 'b' but in option A, there is no such constraint over string (the only thing is that no. of 'a' = no. of 'b' in any order).

---

Option A and Option B are way different, option A states the equal number of a's and b's, but there is no constraint on the order of appearance of a and b. So, the language obtained by option a can have strings like {\(\epsilon\), aabb, abab, aabbab,.....}

Whereas, option B can have strings where a appears first and then b comes and the number of a's and b's are the same. So, the language obtained by option b can have strings like {ab, aabb, aaabbb,....}

Option B is the subset of Option A.

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