Computer Sciences > GATE 2023 > Theory of Computation
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 e, 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?

Explanation
Correct : b
Similar Questions
What is the worst-case time complexity of insertion in an AVL tree?
Which operations on a binary search tree have O(h) complexity?
Compare search complexities of sorted array vs balanced BST.