Consider the pushdown automaton (PDA) P below, which runs on the input…

GATE · 2023 · CS · Computer Science & IT

Consider the pushdown automaton (PDA) P below, which runs on the input alphabet {a, b}, has stack alphabet {⊥, A}, and has three states {s, p, q}, with s being the start state. A transition from state u to state v, labelled c/X/γ, where c is an input symbol or ε, X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v. In the initial configuration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by P?

  1. A.

    {am bn | 1 ≤ m and n < m} 

  2. B.

    {am bn | 0 ≤ n ≤ m}

  3. C.

    {am bn | 0 ≤ m and  0 ≤ n}

  4. D.

    {am | 0 ≤ m} ∪ {bn | 0 ≤ n}

Attempted by 118 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…