GATE Theory of Computation: Context-Free Grammars and Pushdown Automata – Previous Year Questions

19 GATE previous year questions on Context-Free Grammars and Pushdown Automata (Theory of Computation, Computer Science) with answers and explanations, from every paper.

GATE 2017 CS Q20 (1 mark, Multiple choice) – Consider the following context-free grammar over the alphabet = \a, b, c\ with S as the start symbol: S abScT abcT T bT b Which one of the following…
GATE 2017 CS Q44 (2 marks, Multiple choice) – If G is a grammar with productions S SaS aSb bSa SS where S is the start variable, then which one of the following strings is not generated by G?
GATE 2017 CS Q47 (2 marks, Multiple choice) – Consider the context-free grammars over the alphabet \a, b, c\ given below. S and T are non-terminals. G 1: S aSb T, T cT G 2: S bSa T, T cT The…
GATE 2016 CS Q26 (1 mark, Multiple choice) – Which of the following languages is generated by the given grammar? S aS bS
GATE 2016 CS Q52 (2 marks, Multiple choice) – Consider the following context-free grammars: G 1: S aS B, B b bB G 2: S aA bB, A aA B , B bB Which one of the following pairs of languages is…
GATE 2016 CS Q53 (2 marks, Multiple choice) – Consider the transition diagram of a PDA given below with input alphabet = \a, b\ and stack alphabet = \X, Z\. Z is the initial stack symbol. Let L…
GATE 2015 CS Q50 (2 marks, Multiple choice) – Consider the NPDA Q = \q 0, q 1, q 2\, = \0, 1\, = \0, 1, \, , q 0, , F = \q 2\ , where (as per usual convention) Q is the set of states, is the input…
GATE 2018 CS Q45 (2 marks, Multiple choice) – Consider the following languages: I. \ambncpdq m+p=n+q,\ where m,n,p,q0\ II. \ambncpdq m=n and p=q,\ where m,n,p,q0\ III. \ambncpdq m=n=p and p q,\…
GATE 2019 CS Q41 (2 marks, Multiple choice) – Which one of the following languages over =\a,b\ is NOT context-free?
GATE 2026 CS (CS2) Q29 (1 mark, Multiple select) – Which of the following grammars is/are ambiguous?
GATE 2026 CS (CS2) Q48 (2 marks, Multiple select) – Let =\a,b,c,d\ and let L=\ai bj ck dl i,j,k,l 0\. Which of the following constraints ensure(s) that the language is context-free?
GATE 2026 CS (CS1) Q25 (1 mark, Multiple select) – Consider the following grammar where S is the start symbol, and a and b are terminal symbols. S aSbS bS Which of the following statements is/are true?
GATE 2026 CS (CS1) Q52 (2 marks, Multiple select) – Consider the following context-free grammar G: S abaABAbba A aaB BAb bB a b a a B aBb ab In the above grammar, S is the start symbol, a and b are…
GATE 2025 CS (CS1) Q19 (1 mark, Multiple choice) – Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start…
GATE 2024 CS (CS2) Q52 (2 marks, Multiple select) – Consider a context-free grammar G with rules S aS, S aSbS, S c. Let w L(G) and let n a(w), n b(w), n c(w) denote the number of times a,b,c occur in w.…
GATE 2024 CS (CS1) Q59 (2 marks, Numerical answer) – Let G=(V,,S,P) be a context-free grammar in Chomsky Normal Form with =\a,b,c\ and V containing 10 variable symbols including the start symbol S. The…
GATE 2023 CS Q39 (2 marks, Multiple choice) – Consider the context-free grammar G below: S → aSb X; X → aX Xb a b, where S and X are non-terminals, and a and b are terminal symbols. The starting…
GATE 2023 CS Q40 (2 marks, Multiple choice) – Consider the pushdown automaton (PDA) P below, which runs on the input alphabet a, b, has stack alphabet ⊥, A, and has three states s, p, q, with s…
GATE 2021 CS Q61 (2 marks, Numerical answer) – In a pushdown automaton P=(Q,,,,q 0,F), a transition of the form p a, X Y q represents (q,Y)(p,a,X). Consider the following pushdown automaton over…