GATE CSE 2023 Q40: Language accepted by empty stack by a three-state PDA
- Theory of Computation
- 2 marks
- MCQ
- −2/3 if wrong
Question
Consider the pushdown automaton (PDA) below, which runs on the input alphabet , has stack alphabet , and has three states , with being the start state. A transition from state to state , labelled , where is an input symbol or , is a stack symbol, and is a string of stack symbols, represents the fact that in state , the PDA can read from the input, with on the top of its stack, pop from the stack, push in the string on the stack, and go to state . 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 ?
Try it: multiple choice: exactly one correct option
Show answer and explanation
Answer: A (official GATE 2023 final answer key)
Concept used: Acceptance by empty stack: the stack can only be emptied in , and reaching needs an on top.
First step: Note that every move into pops an ; ask how many 's must remain after reading the 's.
Full step-by-step solution
Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.
Share this question
Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key
More Theory of Computation PYQs
- 2026 Session 1 · Q25Ambiguity of S → aSbS | bS | ε
- 2026 Session 1 · Q26Impossible minimal DFA sizes for a 6-state NFA
- 2026 Session 1 · Q51What follows from L1 ∩ L2 and L2 being regular
- 2026 Session 1 · Q52Counts of a's and b's in strings of a given CFG
- 2026 Session 2 · Q13Meaning of a Turing machine deciding a language
- 2026 Session 2 · Q29Which of four grammars are ambiguous