Skip to content
GATEiit

GATE CSE 2023 Q40: Language accepted by empty stack by a three-state PDA

Question

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

PDA: start state s loops on a/⊥/A⊥ and a/A/AA; s goes to p on b/A/ε and to q on ε/A/ε. State p loops on b/A/ε and goes to q on ε/A/ε. State q loops on ε/A/ε and ε/⊥/ε
Tap the figure to enlarge

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

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 2/3 mark in GATE.
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 qq, and reaching qq needs an AA on top.

First step: Note that every move into qq pops an AA; ask how many AA's must remain after reading the bb'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

WhatsAppDownload image

Source: official GATE 2023 CS question paper and final answer key, organised by IIT Kanpur. Question paper · Answer key