Question

Which language can be accepted by a PDA but not by an FA?

• A. \(\{a^*b^*\}\)
• B. \((ab)^*\)
• C. \(\{a^n b^n \mid n\ge0\}\)
• D. \(\{a,b\}^*\)

Hint:

\[ \{a^n b^n\} \] is the classical example of a context-free language that is not regular.

Answer 1

The Correct Option is C

Concept: Finite Automata (FA) recognize regular languages. Pushdown Automata (PDA) recognize context-free languages. Every regular language can be accepted by a PDA, but some context-free languages require stack memory and cannot be accepted by an FA.

Step 1: Examine the language.
Consider \[ L=\{a^n b^n \mid n\ge0\}. \] Examples: \[ ab,\quad aabb,\quad aaabbb. \]

Step 2: Need for memory.
The machine must remember the number of \(a\)'s and compare it with the number of \(b\)'s. Finite automata cannot store an arbitrary count.

Step 3: Use of stack.
A PDA pushes symbols while reading \(a\)'s and pops them while reading \(b\)'s. Thus a PDA can recognize the language.

Step 4: Write the answer.
Hence the language accepted by PDA but not FA is \[ \boxed{\{a^n b^n \mid n\ge0\}} \] Therefore option (C) is correct.