GATE CS 1996 Q1.10 — Regular and Context-free Languages

To determine which of the given languages is regular, we analyze each option based on the memory requirements of a Finite Automaton (FA):

• Option A: $L = \{x \mid x \text{ has an equal number of } a\text{'s and } b\text{'s}\}$
  This language requires comparing the total count of $a$'s with the total count of $b$'s. Since the length of the string is unbounded, a finite automaton would need infinite states to keep track of the difference between the counts. Thus, it is not regular (it is context-free).
• Option B: $L = \{a^n b^n \mid n \geq 1\}$
  This language requires matching the exact number of leading $a$'s with the subsequent $b$'s. Since $n$ can be arbitrarily large, it requires infinite memory (a stack) to count. Thus, it is not regular (it is context-free).
• Option C: $L = \{x \mid x \text{ has more } a\text{'s than } b\text{'s}\}$
  Similar to Option A, this requires comparing the counts of $a$'s and $b$'s, which cannot be done with a finite number of states. Thus, it is not regular (it is context-free).
• Option D: $L = \{a^m b^n \mid m \geq 1, n \geq 1\}$
  Here, the powers $m$ and $n$ are independent. The language simply consists of strings containing one or more $a$'s followed by one or more $b$'s. This can be defined by the regular expression $a^+b^+$ (or $a a^* b b^*$). Since we can easily construct a Deterministic Finite Automaton (DFA) for this language, it is regular.