PDA Design and Basics MCQs: 12 Solved Questions with Explanations

A PDA MCQ often looks like a definition check, but its distractors usually test one of four boundaries: what a transition can inspect, what the stack adds, where nondeterminism matters, and whether final-state acceptance differs from empty-stack acceptance. Each boundary has its stock distractor: a transition that never writes the stack back, a stack capped at a constant, a DPDA claimed equal to every NPDA, and an acceptance mode assumed to change the language class. Work through them alongside structured GATE CS preparation.

1. Build one PDA trace before attempting the MCQs

A PDA configuration records the current state, unread input, and stack contents. A transition inspects the state, the next input symbol or epsilon, and the stack top, then selects a next state and replacement stack string. A finite automaton has no such unbounded stack.

For L = {a^n b^n | n >= 0}, use initial symbol Z0. The transitions are (q0,a,Z0)->(q0,AZ0), (q0,a,A)->(q0,AA), (q0,b,A)->(q1,epsilon), (q1,b,A)->(q1,epsilon), (q1,epsilon,Z0)->(qf,Z0), and (q0,epsilon,Z0)->(qf,Z0), which covers the empty string at n = 0. On aabb, the run is:

(q0, aabb, Z0) -> (q0, abb, AZ0) -> (q0, bb, AAZ0) -> (q1, b, AZ0) -> (q1, epsilon, Z0) -> (qf, epsilon, Z0)

The two a symbols create exactly two A markers. The two b symbols remove exactly two markers. The final epsilon move enters qf without consuming input. This stack behaviour is the key behind CFG and PDA equivalence.

2. Questions 1-3: representation, transition input and grammar power

Question 1: representation of a PDA

Bihar STET 2025.

PDA can be represented with the help of:

A. Instantaneous description

B. Transition diagram

C. Transition table

D. All of these

Answer: D. All of these. (q0, aabb, Z0) is an instantaneous description; a diagram uses the edge a/Z0/AZ0; a table records the same move. The trap is assuming only the diagram is formal.

Question 2: transition-function form

BEL 2023.

In the push down automata, transitional function δ is in the form _____.

A. Q × Σ × Γ → Q

B. Q × Σ → Q

C. Q × (Σ ∪ {λ}) × Γ → (Q, Γ*)

D. Q × Σ → (Q, Γ)

Answer: C. (q0, a, Z0) -> (q0, AZ0) reads state, symbol, and stack top, then returns q0 with replacement AZ0. C permits λ. A never writes the stack back, B ignores the stack and so describes a DFA, and D writes one stack symbol rather than a string. Formally, an NPDA returns a set of (state, stack-string) pairs.

Question 3: which grammars a PDA can recognize

UGC NET 2018.

Pushdown automata can recognize language generated by_________.

A. Only context free grammar

B. Only regular grammar

C. Context free grammar or regular grammar

D. Only context sensitive grammar

Answer: C. Regular languages sit inside CFLs. A PDA can ignore its stack for a*b*, or use it for the nonregular CFL {a^n b^n | n >= 0}.

3. Questions 4-6: finite memory versus stack power

Question 4: a bounded stack

GATE 2002.

The language accepted by a pushdown automaton whose stack is limited to 10 items is best described as:

A. Context-free

B. Regular

C. Deterministic context-free

D. Recursive

Answer: B. Regular. The question fixes no alphabet size, so take three stack symbols as the example. With depth at most 10, the possible stack contents total

1 + 3 + 3^2 + ... + 3^10 = (3^11 - 1) / 2 = 88,573.

A machine with four control states then has 4 × 88,573 = 354,292 reachable configurations, which a finite automaton can encode as states. Large is still finite. A, C and D also hold of a regular language, since every regular language is deterministic context-free and recursive, but only B names the tightest class.

Question 5: equivalence across machine models

GATE 1998.

Regarding the power of recognition of languages, which of the following statements is false?

A. Non-deterministic finite-state automata are equivalent to deterministic finite-state automata.

B. Non-deterministic pushdown automata are equivalent to deterministic pushdown automata.

C. Non-deterministic Turing machines are equivalent to deterministic Turing machines.

D. Multi-tape Turing machines are equivalent to single-tape Turing machines.

Answer: B. Compare the models:

Multiple tapes may change efficiency, not recognition power.

Question 6: the same boundary as a two-statement test

UGC NET 2012.

Given the following statements: (i) The power of deterministic finite state machine and non-deterministic finite state machine are same (ii) The power of deterministic pushdown automaton and non-deterministic pushdown automaton are same Which of the above is the correct statement(s)?

A. Both (i) and (ii)

B. Only (i)

C. Only (ii)

D. Neither (i) nor (ii)

Answer: B. Only (i). DFA equals NFA, but DPDA languages form a proper subset of NPDA languages. Use this as a 15-second check on Question 5.

4. Questions 7-9: deterministic and nondeterministic PDAs

Question 7: class-containment notation

GATE 2005.

Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

A. Df ⊂ Nf and Dp ⊂ Np

B. Df ⊂ Nf and Dp = Np

C. Df = Nf and Dp = Np

D. Df = Nf and Dp ⊂ Np

Answer: D. Equality means equal power; ⊂ means proper subset. Separately, Df = Nf, while Dp ⊂ Np because some NPDA language has no equivalent DPDA.

Question 8: a language needing NPDA choice

GATE 2006.

Which of the following languages is accepted by a non-deterministic pushdown automaton (PDA) but NOT by a deterministic PDA?

A. {aⁿbⁿcⁿ ∣ n≥0}

B. {aˡbᵐcⁿ ∣ l≠m or m≠n}

C. {aⁿbⁿ ∣ n≥0}

D. {aᵐbⁿ∣ m,n≥0}

Answer: B. A is not context-free. A DPDA handles C's marked phase change, and D is regular. For B, an NPDA branches to check l != m or m != n. Thus aabcc, (2,1,2), is accepted, while aabbcc, (2,2,2), is rejected.

Question 9: two deterministic CFLs

UGC NET 2014.

Given the following two languages: L₁ = { aⁿ bⁿ | n > 1 } ∪ {a} L₂ = { w c wᴿ | w ∈ {a, b}* } Which statement is correct?

A. Both L₁ and L₂ are not deterministic

B. L₁ is not deterministic and L₂ is deterministic

C. L₁ is deterministic and L₂ is not deterministic

D. Both L₁ and L₂ are deterministic

Answer: D. In L₁, a, aabb, and aaabbb belong, but ab fails n > 1. In L₂, middle c marks the turn: abcba, with w = ab, is accepted; abcab is rejected. No guess is needed.

5. Questions 10-12: acceptance mode, generated language and the false statement

Question 10: final state versus empty stack

GATE 1999.

Let L_D be the set of languages accepted by a PDA by final state, and L_F be the set of languages accepted by a PDA by empty stack. Which of the following is true?

A. L_D = L_F

B. L_D is a proper subset of L_F

C. L_F is a proper subset of L_D

D. None of the above

Answer: A. L_D = L_F. For ordinary NPDAs, both modes define the same class. One machine ends the aabb trace in qf with Z0; an equivalent one adds an epsilon move that pops Z0. Neither containment is proper, because the conversion runs both ways: a final-state machine gains a drain state that empties the stack, and an empty-stack machine gains a marker below Z0 exposed only on acceptance. So B, C and D all fail.

Question 11: reading the language of a CFG

UGC NET 2013.

The grammar with production rules S → aSb | SS | λ generates language L given by:

A. L = { w ∈ {a, b}* | nₐ(w) = n_b(w) and nₐ(v) ≥ n_b(v) where v is any prefix of w }

B. L = { w ∈ {a, b}* | nₐ(w) = n_b(w) and nₐ(v) ≤ n_b(v) where v is any prefix of w }

C. L = { w ∈ {a, b}* | nₐ(w) ≠ n_b(w) and nₐ(v) ≥ n_b(v) where v is any prefix of w }

D. L = { w ∈ {a, b}* | nₐ(w) ≠ n_b(w) and nₐ(v) ≤ n_b(v) where v is any prefix of w }

Answer: A. Nesting gives S => aSb => aaSbb => aabb; concatenation gives S => SS => ab ab => abab. Across the prefixes of aabb, (nₐ,n_b) is (1,0), (2,0), (2,1), (2,2). The a count never falls behind, and the totals end equal. B reverses the prefix test, which the prefix a already breaks. C and D need unequal totals, but every rule adds one a with each b. Continue with more CFG, CFL and PDA questions.

Question 12: isolate the single false claim

ISRO 2017.

Which one of the following is FALSE?

A. There is a unique minimal DFA for every regular language

B. Every NFA can be converted to an equivalent PDA

C. Complement of every context-free language is recursive

D. Every non-deterministic PDA can be converted to an equivalent deterministic PDA

Answer: D. A is true up to state renaming. B is true because a PDA can simulate an NFA without using its stack. C is true because every CFL is decidable and recursive languages are closed under complement, not because CFLs are closed under complement. D fails because DPDA languages are a proper subset of NPDA languages.

6. Turn the 12 answers into a five-line revision sheet

1. A PDA transition reads a state, optional input, and stack top.

2. PDAs recognize the context-free languages, including all regular languages.

3. A bounded stack collapses the machine to finite-state power.

4. DFA equals NFA, but DPDA is strictly weaker than NPDA.

5. Final-state and empty-stack acceptance are equivalent for NPDAs.

Answer strip: 1-D, 2-C, 3-C, 4-B, 5-B, 6-B, 7-D, 8-B, 9-D, 10-A, 11-A, 12-D

Cover the strip and retry any question whose explanation you cannot reproduce in one sentence.

7. PDA practice: what to do next

Move to mixed Theory of Computation questions only after these boundaries are stable. If you still confuse the core model, follow the sequence in GATE Guidance by Sanchit Sir. If the rules are clear but you need timed retrieval, use the GATE Test Series.