GATE | GATE-CS-2016 (Set 1) | Question 53

Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b}and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

(A) A
(B) B
(C) C
(D) D

Answer: (D)


In the given PDA we can number the states as q1, q2 and q3 from left to right.

The transitions of the PDA are as follows:

  1. (q1, a, Z) ->(q1, XZ )

  2. (q1, a, X) ->(q1, XX )

  3. (q1, b, X) ->(q2, € )

  4. (q2, b, X) –>(q2, € )

  5. (q2, €, Z) ->(q3, Z)

As initial state is the final state hence null string is always accepted by the PDA.
The first two transitions show that state remains q1 (final state) on ‘a’ input alphabet and with every ‘a’ we push X onto the stack. Hence an is always accepted for n≥0.
Transitions 3 and 4 shows that for input alphabet ‘b’ and stack symbol X (i.e. ‘a’ occurred in the string) we can pop X from the stack. Transition 5 shows that we can move to the final state (q3) only when the string is empty and stack symbol is Z. This is possible when we have popped all X from the stack i.e. ‘b’ occurred exactly the same times as ‘a’. Hence anbn is always accepted for n≥0. The language accepted by the PDA is { an | n≥0 } U { anbn | n≥0 } and is a Deterministic CFL.
(anbn | n≥0 is not regular but is accepted by a PDA). Hence option (D).

This solution is contributed by Yashika Arora.

Leave a Reply

Your email address will not be published. Required fields are marked *