GATE CS 2021 (Forenoon) — Question 61

Theory of Computation (TOC)Context-Free Grammars & Push-Down AutomataNAT2 marksHard

In a pushdown automaton \(P = (Q, \Sigma, \Gamma, \delta, q_0, F)\), a transition of the form,
Question image
where \(p, q \in Q\), \(a \in \Sigma \cup \{\epsilon\}\), and \(X, Y \in \Gamma \cup \{\epsilon\}\), represents \((q, Y) \in \delta(p, a, X)\) Consider the following pushdown automaton over the input alphabet \(\Sigma \{a, b\}\) and stack alphabet \(\Gamma = \{\#, A\}\).
Question image
The number of strings of length 100 accepted by the above pushdown automaton is _________.
Practise the full 2021-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.
Practise more on Context-Free Grammars & Push-Down AutomataTimed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group