GATE CS 1999 Q1.6 — Context-free Grammars and Push-down Automata

The question asks about the relationship between the class of languages accepted by Pushdown Automata (PDAs) using two different acceptance criteria:

• $L_1$: The set of all languages accepted by a PDA by final state. This is precisely the class of Context-Free Languages (CFLs).
• $L_2$: The set of all languages accepted by a PDA by empty stack. This is also precisely the class of Context-Free Languages (CFLs).

For any context-free language $L$, we can construct a PDA that accepts $L$ by final state, and we can also construct a PDA that accepts $L$ by empty stack. Thus, the expressive power of both acceptance mechanisms is identical.

Therefore, the set of languages defined by both classes is the same:

Hence, the correct option is A.