Question

Consider the language $L = \{a^n b^n \mid n \geq 0\}$. Choose the computational model that can recognize this language.

• A. Finite Automata
• B. Pushdown Automata
• C. Turing Machine with no Stack
• D. Linear Search Algorithm

Hint:

Pumping Lemma for Regular Languages is the formal tool used to prove that $a^n b^n$ cannot be recognized by a Finite Automaton.

Answer 1

The Correct Option is B

Concept: The language $L = \{a^n b^n\}$ is the classic example of a Context-Free Language that is NOT Regular.
• Finite Automata: Cannot "count" or remember how many 'a's it saw to match with 'b's.
• Pushdown Automata (PDA): Uses a Stack to keep track of counts.

Step 1: Why Finite Automata fails.
A Finite Automaton has a fixed, finite number of states. To recognize $a^n b^n$ for any $n$, it would need a different state for every possible value of $n$. Since $n$ can be infinite, a finite machine cannot handle it.

Step 2: How the PDA succeeds.
As the PDA reads 'a's, it "Pushes" them onto the stack. When it starts seeing 'b's, it "Pops" one 'a' for every 'b' it encounters. If the stack is empty exactly when the input ends, the string is accepted.

Step 3: Conclusion.
The Stack memory is what allows the PDA to solve the matching problem. This makes the PDA the appropriate model for this specific language.