Skip to content
GATEiit

GATE CSE 2021 Set 1 Q61: Strings of length 100 accepted by a PDA

Question

In a pushdown automaton P=(Q,Σ,Γ,δ,q0,F)P = (Q, \Sigma, \Gamma, \delta, q_0, F), a transition of the form p→a, X→Yqp \xrightarrow{a,\ X \to Y} q, 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 ________.

PDA with states q0 (start), q1, q2 and accepting q3. q0 to q1 on ε, ε → #. q1 has a self-loop a, ε → A. q1 to q2 on ε, ε → ε. q2 has a self-loop b, A → ε. q2 to q3 on ε, A → A
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 50 (official GATE 2021 final answer key)

Concept used: Trace the language: push an A per a, pop an A per b, and accept only if an A is still on the stack.

First step: The accepted strings are anbma^n b^m with n>mn > m; count those with n+m=100n + m = 100.

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 2021 Set 1 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2021 Set 1 questions →