Let L_D be the set of languages accepted by a PDA by final state, and L_F be…
1999
Let L_D be the set of languages accepted by a PDA by final state, and L_F be the set of languages accepted by a PDA by empty stack. Which of the following is true?
- A.
L_D = L_F
- B.
L_D is a proper subset of L_F
- C.
L_F is a proper subset of L_D
- D.
None of the above
Attempted by 16 students.
Show answer & explanation
Correct answer: A
The correct answer is: L_D = L_F.
For ordinary nondeterministic pushdown automata, the two standard acceptance modes are equivalent:
- acceptance by final state
- acceptance by empty stack
If a language is accepted by a PDA by final state, we can construct another PDA that accepts the same language by empty stack. Similarly, if a language is accepted by empty stack, we can construct an equivalent PDA that accepts by final state.
Therefore both L_D and L_F describe exactly the class of context-free languages accepted by PDAs.
Hence, L_D = L_F.