Pushdown Automata
Pushdown Automata(Theory of Computation) — 100 Tricky MCQs for GATE
Q1. A Pushdown Automaton (PDA) differs from a Finite Automaton (FA) by having:
A) A second input tape
B) A stack
C) A counter
D) A queue
Answer: B
Explanation: PDA includes a stack, enabling recognition of context-free languages.
Q2. Which of the following languages is accepted by a PDA but not by any DFA?
A) {aⁿbⁿ | n ≥ 0}
B) {aⁿ | n ≥ 0}
C) {aⁿbᵐ | n, m ≥ 0}
D) {aⁿbⁿcⁿ | n ≥ 0}
Answer: A
Explanation: PDA can recognize aⁿbⁿ (CFL), which DFA cannot due to memory limits.
Q3. PDA can be used to recognize:
A) Regular languages only
B) Context-free languages only
C) Context-sensitive languages
D) Recursive languages
Answer: B
Explanation: PDAs recognize all and only the context-free languages.
Q4. Which mechanism allows PDA to remember unbounded information?
A) Input symbols
B) Stack
C) State transitions
D) Output symbols
Answer: B
Explanation: Stack provides unbounded memory through push/pop operations.
Q5. PDA is more powerful than DFA because:
A) It uses recursion
B) It has extra storage (stack)
C) It can backtrack
D) It uses nondeterminism
Answer: B
Explanation: Stack allows PDA to store count or sequence information.
Q6. PDA accepting by empty stack is equivalent to PDA accepting by:
A) Rejection
B) Final state
C) Both A and B
D) None
Answer: B
Explanation: Both acceptance methods are equivalent for non-deterministic PDAs.
Q7. Deterministic PDA (DPDA) cannot accept which language?
A) Regular languages
B) Deterministic context-free languages
C) Palindromes
D) ε
Answer: C
Explanation: Palindromes require nondeterminism; DPDA cannot handle them.
Q8. A PDA uses which data structure?
A) Stack
B) Queue
C) Tree
D) Array
Answer: A
Explanation: PDA’s stack enables last-in-first-out operations.
Q9. PDA for {aⁿbⁿ | n ≥ 0} pushes ‘a’ and pops for ‘b’. For equal count, stack ends:
A) Non-empty
B) Empty
C) Overflow
D) Undefined
Answer: B
Explanation: Equal numbers cause all pushed symbols to be popped → empty stack.
Q10. PDA that accepts aⁿbⁿ by final state must end in:
A) Initial state
B) Final state with empty stack
C) Final state with non-empty stack
D) Trap state
Answer: C
Explanation: When accepting by final state, the stack may remain non-empty.
Q11. PDA equivalent to CFG G can be constructed by:
A) Reading grammar backwards
B) Simulating leftmost derivations
C) Simulating rightmost derivations
D) Removing recursion
Answer: B
Explanation: PDA simulates leftmost derivations of CFG.
Q12. PDA for language {wwᴿ | w ∈ {a,b}*} requires:
A) One stack
B) Two stacks
C) Queue
D) No stack
Answer: B
Explanation: Palindromes require comparison ⇒ two stacks or TM.
Q13. Which of the following is not a context-free language?
A) {aⁿbⁿ}
B) {aⁿbⁿcⁿ}
C) {aⁱbʲcᵏ | i = j or j = k}
D) {aⁱbʲcᵏ | i = j, k arbitrary}
Answer: B
Explanation: Requires two simultaneous counters; not context-free.
Q14. PDA transitions are defined by:
A) δ: Q × Σ → Q
B) δ: Q × Σ × Γ → Q × Γ*
C) δ: Q × Γ → Q
D) δ: Q → Γ
Answer: B
Explanation: PDA transition depends on current state, input, and top of stack.
Q15. PDA’s stack alphabet is denoted by:
A) Σ
B) Γ
C) Q
D) δ
Answer: B
Explanation: Σ is input alphabet; Γ is stack alphabet.
Q16. Which PDA acceptance mode can accept ε?
A) By final state only
B) By empty stack only
C) Both
D) None
Answer: C
Explanation: PDA can be designed to accept ε in either mode.
Q17. The number of states in a PDA recognizing aⁿbⁿ by empty stack can be:
A) 1
B) 2
C) 3
D) 4
Answer: B
Explanation: One for pushing a’s, one for popping b’s.
Q18. Deterministic PDA languages are:
A) Closed under union
B) Not closed under union
C) Closed under complement
D) Both B and C
Answer: D
Explanation: DPDA languages are not closed under union or complement.
Q19. A PDA with k stacks is equivalent to:
A) DFA (for k=0)
B) TM (for k=2)
C) NFA (for k=1)
D) All of these
Answer: D
Explanation: 0-stack → DFA, 1-stack → PDA, 2-stacks → TM.
Q20. Which of the following cannot be accepted by a PDA?
A) Palindromes over {a,b}
B) aⁿbⁿ
C) aⁿbᵐ | n≠m
D) aⁿbⁿcⁿ
Answer: D
Explanation: Requires simultaneous comparison of two counters.
Q21. PDA for {aⁿbᵐ | n ≤ m} works by:
A) Pushing all a’s and popping for equal number of b’s
B) Guessing boundary where popping stops
C) Using ε-transitions after some b’s
D) All of these
Answer: D
Explanation: PDA can nondeterministically guess when to stop popping.
Q22. Deterministic PDA (DPDA) is not equivalent to:
A) Non-deterministic PDA (NPDA)
B) Finite automaton
C) Context-free grammar
D) Regular grammar
Answer: A
Explanation: DPDA ⊊ NPDA; NPDA is strictly more powerful.
Q23. PDA can simulate:
A) Finite automaton
B) Context-free grammar
C) Both A and B
D) None
Answer: C
Explanation: PDA can simulate both a CFG and a DFA.
Q24. A PDA accepting by empty stack can be converted to one accepting by final state by:
A) Adding ε-transitions
B) Adding a new final state
C) Both A and B
D) Removing ε-transitions
Answer: C
Explanation: Add a new final state reachable when stack becomes empty.
Q25. Which of the following statements is true?
A) Every regular language is CFL.
B) Every CFL is regular.
C) PDA cannot recognize any regular language.
D) PDA recognizes recursive languages.
Answer: A
Explanation: Regular ⊂ Context-free.
Q26. PDA for aⁿbⁿcⁿ cannot be built because:
A) Stack alphabet insufficient
B) Stack can’t compare two symbols simultaneously
C) PDA nondeterministic
D) None
Answer: B
Explanation: PDA has only one stack; can’t handle two equalities simultaneously.
Q27. PDA transitions can include ε on:
A) Input only
B) Stack only
C) Both input and stack
D) Neither
Answer: C
Explanation: PDA allows ε-transitions for both input and stack symbol.
Q28. PDA for aⁿbⁿ uses stack symbols to:
A) Store ‘b’s
B) Store ‘a’s
C) Store both
D) Store none
Answer: B
Explanation: PDA pushes ‘a’s to match ‘b’s later.
Q29. Which of the following is not true?
A) PDA is equivalent to CFG.
B) PDA and CFG both accept CFL.
C) PDA can be deterministic for all CFL.
D) PDA can be non-deterministic.
Answer: C
Explanation: Some CFLs require nondeterminism (e.g., palindromes).
Q30. PDA can be formally defined as:
A) 5-tuple
B) 6-tuple
C) 7-tuple
D) 8-tuple
Answer: C
Explanation: PDA = (Q, Σ, Γ, δ, q₀, Z₀, F).
Q31. For PDA with empty stack acceptance, final states are:
A) Mandatory
B) Optional
C) Forbidden
D) Irrelevant
Answer: B
Explanation: Acceptance depends only on empty stack, not final states.
Q32. Which of the following pairs is not equivalent in power?
A) NFA and DFA
B) DPDA and NPDA
C) CFG and NPDA
D) PDA and CFG
Answer: B
Explanation: DPDA ⊊ NPDA.
Q33. Which property is not true for PDA languages?
A) Closed under union
B) Closed under intersection
C) Closed under concatenation
D) Closed under Kleene star
Answer: B
Explanation: CFLs are not closed under intersection or complement.
Q34. Which of these can’t be accepted by PDA?
A) {ww | w ∈ {a,b}} B) {wwᴿ | w ∈ {a,b}}
C) {aⁿbⁿ}
D) {aᵐbⁿ | m ≠ n}
Answer: A
Explanation: {ww} is not context-free.
Q35. For language {aⁱbʲ | i < j}, PDA must:
A) Guess when to stop popping
B) Push extra b’s
C) Reject extra a’s
D) None
Answer: A
Explanation: PDA uses nondeterminism to stop popping before all b’s processed.
Q36. PDA for even-length palindromes requires:
A) One stack
B) Two stacks
C) Queue
D) No memory
Answer: B
Explanation: Two stacks needed to compare both halves.
Q37. In PDA, top of stack represents:
A) Most recently pushed symbol
B) Least recently pushed symbol
C) Input symbol
D) None
Answer: A
Explanation: Stack operates in LIFO manner.
Q38. Which machine is more powerful than PDA?
A) DFA
B) Turing Machine
C) NFA
D) Regular Grammar
Answer: B
Explanation: TM > PDA > DFA hierarchy.
Q39. PDA can simulate recursion because of:
A) Its nondeterminism
B) Stack memory
C) State control
D) Input reading
Answer: B
Explanation: Stack allows recursive-like storage of calls.
Q40. PDA for {aⁿbⁿ | n≥0} has transitions that:
A) Push for a’s, pop for b’s
B) Pop for a’s, push for b’s
C) Push for both
D) None
Answer: A
Explanation: Standard PDA behavior for equal matching languages.
Q41. PDA and CFG are equivalent in:
A) Expressive power
B) Determinism
C) Computation time
D) None
Answer: A
Explanation: Both represent context-free languages.
Q42. PDA for {aⁱbʲ | i = 2j} requires:
A) Single counter via stack
B) Multiple stacks
C) Queue
D) TM
Answer: A
Explanation: PDA can simulate double counting via pushing 2 per b.
Q43. PDA cannot perform which operation on its stack?
A) Push
B) Pop
C) Peek
D) Random access
Answer: D
Explanation: Stack allows only LIFO, not arbitrary access.
Q44. DPDA cannot recognize:
A) Balanced parentheses
B) Palindromes
C) aⁿbⁿ
D) Regular languages
Answer: B
Explanation: Palindrome checking needs nondeterminism.
Q45. PDA for {aⁿbⁿcᵐ | n, m ≥ 0} needs to:
A) Push a’s, pop b’s, ignore c’s
B) Push all symbols
C) Pop all symbols
D) Reject all
Answer: A
Explanation: PDA handles first part aⁿbⁿ, ignores remaining c’s.
Q46. For PDA with transitions δ(q, a, X) = (q’, YZ), stack action is:
A) Replace X with YZ
B) Pop Y
C) Push X
D) Ignore input
Answer: A
Explanation: X is popped and replaced by string YZ.
Q47. PDA accepts {aⁿbᵐ | n ≥ m} by:
A) Guessing cutoff point
B) Popping b’s until stack empty
C) Pushing for a’s, popping for b’s
D) All of these
Answer: D
Explanation: PDA can nondeterministically guess valid stopping point.
Q48. Number of components in PDA tuple = ?
A) 5
B) 6
C) 7
D) 8
Answer: C
Explanation: PDA = (Q, Σ, Γ, δ, q₀, Z₀, F).
Q49. PDA for {aⁿbⁿcⁿ} requires:
A) 1 stack
B) 2 stacks
C) 3 stacks
D) Queue
Answer: B
Explanation: Two stacks required for double equality.
Q50. Which of the following can be recognized by DPDA?
A) aⁿbⁿ
B) Palindromes
C) wwᴿ
D) aⁿbⁿcⁿ
Answer: A
Explanation: aⁿbⁿ is deterministic CFL.
Q51. PDA for {aⁿbⁿ | n≥0} initially pushes:
A) a’s
B) b’s
C) both
D) none
Answer: A
Explanation: Push a’s, pop when matching b’s appear.
Q52. DPDA and NPDA are equivalent in power?
A) Yes
B) No
C) Sometimes
D) For deterministic languages only
Answer: B
Explanation: NPDA strictly more powerful.
Q53. PDA for language with equal number of a’s and b’s but unordered cannot exist because:
A) Stack works in LIFO
B) Stack limited alphabet
C) PDA non-deterministic
D) Language not CFL
Answer: D
Explanation: Equal but unordered count → non-context-free.
Q54. PDA transition δ(q, ε, Z₀) = (p, Z₀) means:
A) ε-move without changing stack
B) Pop Z₀
C) Push Z₀ twice
D) Reject ε
Answer: A
Explanation: ε-transition with same symbol implies no stack change.
Q55. PDA equivalent to grammar S → aSb | ε uses stack to:
A) Store a’s
B) Match b’s
C) Both
D) None
Answer: C
Explanation: Push a’s and pop when matching b’s appear.
Q56. Language accepted by PDA is:
A) Regular
B) Context-free
C) Recursive
D) Context-sensitive
Answer: B
Explanation: PDA ⇔ CFL.
Q57. PDA cannot check if:
A) Parentheses balanced
B) Number of a’s equals b’s equals c’s
C) aⁿbⁿ
D) Empty input
Answer: B
Explanation: Triple equality requires 2 stacks (not PDA).
Q58. PDA reading input left-to-right:
A) Must end with empty stack
B) Must end at final state
C) Either condition can be used
D) None
Answer: C
Explanation: PDA can accept by either empty stack or final state.
Q59. PDA can simulate which phase of a compiler?
A) Lexical analysis
B) Parsing
C) Code generation
D) Optimization
Answer: B
Explanation: Parsing uses stack-based syntax checking.
Q60. Which is true for PDA?
A) It can recognize only deterministic CFGs
B) It can recognize all CFLs
C) Stack alphabet equals input alphabet
D) Stack not needed
Answer: B
Explanation: PDA recognizes all context-free languages.
Q61. PDA for the language {aⁿbⁿcᵐ | n, m ≥ 0} will:
A) Push for a’s, pop for b’s, ignore c’s
B) Push for all symbols
C) Pop for a’s
D) None
Answer: A
Explanation: PDA only checks aⁿbⁿ portion; c’s do not affect stack.
Q62. Which of the following is true about PDA?
A) Every DPDA language is regular
B) DPDA = NPDA
C) Every DPDA language is deterministic CFL
D) PDA cannot accept ε
Answer: C
Explanation: DPDAs accept deterministic context-free languages.
Q63. PDA and CFG equivalence is proved by:
A) Constructing CFG → PDA
B) Constructing PDA → CFG
C) Both A and B
D) None
Answer: C
Explanation: Equivalence shown by constructing both ways.
Q64. PDA can recognize palindromes of even length by:
A) Guessing mid-point
B) Determinism
C) Two stacks
D) Queue
Answer: A
Explanation: PDA guesses midpoint nondeterministically.
Q65. PDA stack alphabet (Γ) includes:
A) Input symbols only
B) Stack symbols only
C) Both input and stack markers
D) None
Answer: C
Explanation: Γ includes symbols used for pushing/popping plus Z₀.
Q66. PDA transition function δ returns:
A) Single state
B) Set of state–stack pairs
C) Single stack symbol
D) None
Answer: B
Explanation: δ : Q × (Σ ∪ {ε}) × Γ → P(Q × Γ*).
Q67. PDA for {aⁿbⁿ | n even} can be modified by:
A) Using extra symbol
B) Marking parity via stack
C) Doubling pushes per pair
D) None
Answer: B
Explanation: Stack can store parity markers (e.g., X for every pair of a’s).
Q68. PDA cannot be minimized like DFA because:
A) PDA is nondeterministic
B) Stack complicates equivalence
C) Transitions are infinite
D) All of these
Answer: D
Explanation: PDA minimization undecidable due to stack behavior.
Q69. PDA acceptance by empty stack ensures:
A) Stack empty at input end
B) PDA halted
C) All states final
D) None
Answer: A
Explanation: Empty stack indicates successful input balancing.
Q70. PDA can simulate recursion depth via:
A) States
B) Stack height
C) Input length
D) Transition count
Answer: B
Explanation: Each recursive call represented by push, return by pop.
Q71. PDA cannot recognize language where dependency is:
A) Sequential
B) Nested
C) Crossed
D) Balanced
Answer: C
Explanation: PDA can’t handle crossing dependencies, e.g., {aⁿbᵐcⁿdᵐ}.
Q72. Which language is not deterministic context-free?
A) {aⁿbⁿ}
B) {wwᴿ}
C) Balanced parentheses
D) {aⁿbᵐ | n ≠ m}
Answer: B
Explanation: Palindrome language requires nondeterminism.
Q73. PDA uses Z₀ to:
A) Mark top of stack
B) Mark bottom of stack
C) Mark mid-point
D) Replace all stack symbols
Answer: B
Explanation: Z₀ indicates initial stack bottom marker.
Q74. PDA for {aⁿbⁿ | n≥1} on input “aaabbb”:
A) Accepts
B) Rejects
C) Hangs
D) Depends on nondeterminism
Answer: A
Explanation: Equal count ⇒ accepted.
Q75. PDA accepting {aⁿbⁿ | n≥0} has stack contents after reading “aaa”:
A) Three a’s
B) Two a’s
C) Empty
D) Undefined
Answer: A
Explanation: Three pushes before b’s are processed.
Q76. PDA cannot recognize {aⁿbᵐ | n ≠ m} deterministically because:
A) Requires two comparisons
B) Stack emptiness ambiguous
C) Input undefined
D) Grammar ambiguous
Answer: B
Explanation: Stack empty/non-empty not sufficient for inequality.
Q77. PDA for {aⁿbⁿcᵏ | n,k ≥ 0} is:
A) Context-free
B) Regular
C) Context-sensitive
D) Recursive
Answer: A
Explanation: Can be expressed via PDA pushing for a’s, popping for b’s.
Q78. PDA for {aⁿbⁿcⁿdⁿ} needs:
A) 1 stack
B) 2 stacks
C) 3 stacks
D) TM
Answer: B
Explanation: Two stacks enough for double equality.
Q79. PDA equivalent to CFG S → aSb | ε uses which operation?
A) Push a on ‘a’, pop on ‘b’
B) Pop on ‘a’, push on ‘b’
C) Push both
D) None
Answer: A
Explanation: Matching a–b pattern via push/pop.
Q80. For PDA with δ(q₀, ε, Z₀) = (q₁, XZ₀), operation is:
A) Replace Z₀ with XZ₀
B) Push X
C) Both A and B
D) None
Answer: C
Explanation: ε-transition pushing X above Z₀.
Q81. PDA recognizing {aⁿbⁿ | n≥0} halts with:
A) Empty stack
B) Final state
C) Both possible
D) None
Answer: C
Explanation: Acceptance can be defined by either condition.
Q82. PDA can simulate which data structure?
A) Stack
B) Queue
C) Array
D) List
Answer: A
Explanation: PDA’s memory is precisely a stack.
Q83. A PDA with two stacks is equivalent to:
A) DFA
B) Turing Machine
C) CFG
D) Linear bounded automaton
Answer: B
Explanation: Two stacks provide TM power.
Q84. PDA accepting {aⁱbʲ | i > j} must:
A) Push more than pop
B) Pop more than push
C) Empty stack
D) None
Answer: A
Explanation: More a’s means leftover symbols in stack.
Q85. PDA cannot differentiate between:
A) Equal number of a’s and b’s
B) Equal number of a’s and c’s separated by b’s
C) Balanced parentheses
D) aⁿbⁿ pattern
Answer: B
Explanation: Requires cross-dependency tracking → not CFL.
Q86. PDA and TM differ because:
A) PDA uses stack; TM uses tape
B) PDA is deterministic always
C) PDA can loop infinitely
D) PDA accepts recursive languages
Answer: A
Explanation: Stack vs infinite tape memory model difference.
Q87. PDA for {aⁿbⁿcᵐ | m ≠ n} is:
A) Context-free
B) Context-sensitive
C) Regular
D) Recursive
Answer: B
Explanation: Context-free PDAs can’t enforce inequality constraints.
Q88. DPDA languages are closed under:
A) Union
B) Complement
C) Intersection
D) None
Answer: B
Explanation: Deterministic CFLs are closed under complement but not union.
Q89. NPDA languages are closed under:
A) Complement
B) Intersection
C) Union
D) None
Answer: C
Explanation: Non-deterministic CFLs closed under union, concatenation, Kleene star.
Q90. PDA for {aⁿbⁿ | n odd} differs by:
A) Checking parity
B) Using extra marker
C) Guessing start point
D) Both A and B
Answer: D
Explanation: Stack symbol used to record odd parity.
Q91. PDA is more powerful than DFA because:
A) Stack provides memory
B) More states
C) Nondeterminism
D) Transition count
Answer: A
Explanation: Stack allows context-free recognition.
Q92. PDA can’t accept {aⁿbⁿcⁿ} because:
A) Needs 2 stacks
B) Needs queue
C) Stack not sufficient
D) All of these
Answer: D
Explanation: One stack cannot compare two dependencies simultaneously.
Q93. PDA that ignores input while pushing accepts:
A) Infinite strings
B) ε
C) Non-empty only
D) All possible strings
Answer: B
Explanation: PDA can accept ε by not reading input.
Q94. In PDA, transitions depend on:
A) Input symbol
B) Top of stack
C) Current state
D) All of these
Answer: D
Explanation: δ(q, a, X) considers all three parameters.
Q95. PDA without stack reduces to:
A) DFA
B) NFA
C) TM
D) LBA
Answer: B
Explanation: Without stack, PDA ≈ NFA.
Q96. PDA is best suited for:
A) Tokenizing
B) Syntax parsing
C) Optimization
D) Code generation
Answer: B
Explanation: PDA models parser stack behavior in compilers.
Q97. PDA halts if:
A) Input exhausted
B) Stack empty
C) No valid transition
D) Any of the above
Answer: D
Explanation: PDA halts when no transition available.
Q98. A PDA that accepts by final state may have:
A) Non-empty stack
B) Empty stack
C) Either
D) None
Answer: C
Explanation: Acceptance independent of stack emptiness.
Q99. PDA for {aⁱbʲcᵏ | i = j or j = k} is:
A) Context-free
B) Not context-free
C) Regular
D) Recursive
Answer: A
Explanation: Union of two CFLs (each aⁿbⁿc, abⁿcⁿ) ⇒ CFL.
Q100. PDA for arithmetic expressions with balanced parentheses accepts:
A) Context-free language
B) Context-sensitive language
C) Regular language
D) Recursive enumerable
Answer: A
Explanation: Balanced expressions ⇒ CFL recognized by PDA.
About the Author
