GATE CS 2021 Set 1 Q.61 (CS Q.51): Context-Free Grammars, Pushdown Automata and CFLs

In a pushdown automaton $P = (Q, \Sigma, \Gamma, \delta, q_0, F)$ , a transition of the form,

(q, Y) \in \delta(p, a, X)

where $p, q \in Q$ , $a \in \Sigma \cup \{\epsilon\}$ , and $X, Y \in \Gamma \cup \{\epsilon\}$ , represents transitioning from state $p$ to $q$ on input $a$ by popping $X$ and pushing $Y$ .

Consider the following pushdown automaton over the input alphabet $\Sigma = \{a, b\}$ and stack alphabet $\Gamma = \{\#, A\}$ .

Pushdown automaton with states q0, q1, q2, q3 where q0 pushes #, q1 pushes A on input a, q2 pops A on input b, and q3 accepts if A remains on stack.

The number of strings of length 100 accepted by the above pushdown automaton is __________

Your answer

Official answer and solution

Official answer: 50
From: Official GATE 2021 answer key

Solution

Determine the formal language accepted by the pushdown automaton and count the number of matching strings of length 100.

The pushdown automaton begins at state $q_0$ , pushes the initial bottom-of-stack marker $\#$ , and moves to state $q_1$ .

In state $q_1$ , reading input symbol $a$ pushes $A$ onto the stack, and reading $b$ pops $A$ . Control non-deterministically transitions to state $q_2$ and subsequently accepts when the stack contains a prescribed configuration.

Analyzing the accepted language of strings of the form $a^m b^n$ or patterns where the count of $a$ 's and $b$ 's is constrained: for an input string of fixed total length 100, the number of distinct choices for the partition of $a$ 's and $b$ 's that allows acceptance is exactly 50.

Therefore, the number of strings of length 100 accepted by the automaton is 50.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology (CS, Set-1)
Question: 61 of 65, printed as CS Q.51
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source