Question

A pushdown automaton differs from a finite automaton due to the presence of a _______ that helps in handling nested structures.

• A. Queue
• B. Stack
• C. Heap
• D. Register

Hint:

The formal definition of a PDA includes a "Stack Alphabet" ($\Gamma$), which is a set of symbols that can be pushed onto the stack, distinct from the input alphabet.

Answer 1

The Correct Option is B

Concept: The primary limitation of a Finite Automaton (FA) is its lack of external memory. It can only "remember" information through its states.
• Finite Automaton: State-based memory only (cannot count to infinity).
• Pushdown Automaton (PDA): FA combined with a Stack (LIFO memory).
• Nesting: Structures like balanced parentheses or $a^n b^n$ require a "memory" to store markers and retrieve them in reverse order.

Step 1: Understanding the deficiency of Finite Automata.
An FA cannot recognize languages that require matching or counting. For example, it cannot check if the number of opening brackets equals closing brackets.

Step 2: Identifying the role of the Stack.
A Stack provides a Pushdown Automaton with "infinite" auxiliary memory. It allows the machine to "push" a symbol when a structure opens. It then "pops" that symbol when the corresponding structure closes.

Step 3: Conclusion on Nested Structures.
Because nesting follows a Last-In-First-Out (LIFO) pattern, a Stack is the perfect tool. Therefore, the Stack is the defining difference that enables PDA to handle CFGs.