GateAI
Context-Free Grammars and PDAs

GATE CSE 2021 Set 1 · Q51

NAT2 marksMedium

Time

In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F)P = (Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form, where p,q∈Qp, q \in Q, a∈Σ∪{ϵ}a \in \Sigma \cup \{\epsilon\}, and X,Y∈Γ∪{ϵ}X, Y \in \Gamma \cup \{\epsilon\}, represents (q,Y)∈δ(p,a,X).(q, Y) \in \delta(p, a, X). Consider the following pushdown automaton over the input alphabet Σ={a,b}\Sigma = \{a, b\} and stack alphabet Γ={#,A}\Gamma = \{\#, A\}. The number of strings of length 100 accepted by the above pushdown automaton is _____.

GATE CSE 2021 Set 1 Q51 diagram 1
GATE CSE 2021 Set 1 Q51 diagram 2

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 50

Context-Free Grammars and PDAs

Let us analyze the language accepted by the given pushdown automaton (PDA):

  1. Initial transition: From the start state q0q_0, the transition ϵ,ϵ→#\epsilon, \epsilon \to \# moves to state q1q_1 and pushes the bottom-of-stack marker #\# onto the stack.

  2. State q1q_1: The self-loop a,ϵ→Aa, \epsilon \to A reads input symbol aa and pushes AA onto the stack without popping anything. Thus, reading nn occurrences of aa pushes nn symbols AA onto the stack (n≥0n \ge 0).

  3. Transition q1→q2q_1 \to q_2: An ϵ\epsilon-transition ϵ,ϵ→ϵ\epsilon, \epsilon \to \epsilon moves to state q2q_2 without altering the stack.

  4. State q2q_2: The self-loop b,A→ϵb, A \to \epsilon reads input symbol bb and pops one symbol AA from the stack. If mm occurrences of bb are read, mm symbols AA are popped (m≥0m \ge 0).

  5. Transition q2→q3q_2 \to q_3 (Final state): The transition ϵ,A→A\epsilon, A \to A moves to the accepting state q3q_3 without consuming any input, provided the top of the stack is AA. This requires at least one AA to remain on top of the stack, which means:

    n−m≥1  ⟹  n>mn - m \ge 1 \implies n > m

Thus, the PDA accepts strings of the form w=anbmw = a^n b^m such that n>m≥0n > m \ge 0.

We are asked to find the number of accepted strings of length 100100:

n+m=100n + m = 100

Substituting n=100−mn = 100 - m into the inequality n>mn > m:

100−m>m  ⟹  2m<100  ⟹  m<50100 - m > m \implies 2m < 100 \implies m < 50

Since mm is an integer and m≥0m \ge 0, the possible values of mm are:

m∈{0,1,2,…,49}m \in \{0, 1, 2, \dots, 49\}

There are 5050 possible values for mm, and each corresponds to a unique string a100−mbma^{100-m} b^m.

Therefore, the number of accepted strings of length 100100 is 50.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Context-Free Grammars and PDAs previous year question is Q51 of the GATE CSE 2021 Set 1 paper. Find more GATE CSE PYQs on Context-Free Grammars and PDAs in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Context-Free Grammars and PDAs PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Context-Free Grammars and PDAs in GATE CSE

Context-Free Grammars and PDAs has 26 GATE CSE PYQs across 17 papers from 2011 to 2026. 2 of them are 2-mark NAT questions like this one, and GATE CSE 2021 Set 1 has 2.

How GATE tests Context-Free Grammars and PDAs

More from GATE CSE 2021 Set 1

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2021 Set 1 · Q51 · NAT

In a pushdown automaton P = (Q, , , , q0, F), a transition of the form, where p, q ∈ Q, a ∈ ∪ { }, and X, Y ∈ ∪ { }, represents (q, Y) ∈ (p, a, X). Consider the following pushdown automaton over the input alphabet = {a, b} and stack alphabet = {\#, A}. The number of strings of length 100 accepted by the above pushdown automaton is …

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.