GATEverse Practice, past papers & mock tests
GATE 2023 · CS - Forenoon
Theory of ComputationPush Down Automata: CFL & DCFLhardMCQ2 marks
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet {a,b}, has stack alphabet {bottom-marker, A}, and has three states {s,p,q}, with s being the start state. In the initial configuration the stack has only the bottom-marker in it. The PDA accepts by empty stack. Transitions: at state s, on reading 'a' with bottom-marker on top of stack, pop it and push 'A bottom-marker' (self-loop at s); on reading 'a' with 'A' on top, pop it and push 'AA' (self-loop at s); on reading 'b' with 'A' on top, pop it and push nothing, moving from s to p. At state p, on reading 'b' with 'A' on top, pop it and push nothing (self-loop at p). On ε with 'A' on top, pop it and push nothing, moving from s to q and also from p to q. At state q, on ε with 'A' on top, pop it (self-loop); on ε with bottom-marker on top, pop it (self-loop). Which one of the following options correctly describes the language accepted by P?
Save your progress

Related Theory of Computation PYQs