Let L_F be the set of all languages accepted by a PDA by final state and L_e be the set of all languages accepted by empty stack. Which of the following is true? A. L_F = L_e B. L_F subset L_e C. L_e subset L_F D. None

GATE 1999 · Theory of Computation · Pushdown Automata · medium

Answer: A. L_F = L_e

  1. From empty stack to final state: L_e subset L_F: Given PDA M_e = (Q, Sigma, Gamma, delta, q_0, Z_0, phi) accepting by empty stack. Construct PDA M_F: add a new start state p_0, new final state p_f, new bottom marker X_0. From p_0, push X_0 and enter q_0 (epsilon-transition). When M_e would empty its stack (reaching X_0 on bottom), instead transition to p_f. This construction shows any language in L_e is also in L_F.
  2. From final state to empty stack: L_F subset L_e: Given PDA M_F = (Q, Sigma, Gamma, delta, q_0, Z_0, F) accepting by final state. Construct PDA M_e: add new start state p_0, new state p_e, new bottom marker X_0. From p_0, push X_0 and enter q_0. From any final state q in F, add epsilon-transitions to p_e that pop everything off the stack (including X_0), accepting by empty stack.
  3. Conclude L_F = L_e: Since L_e subset L_F (step 1) and L_F subset L_e (step 2), we have L_F = L_e. Both equal exactly the class of context-free languages.