The GATE Grind

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

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

32 questions worth 55 marks in all (9 1-mark, 23 2-mark). Asked between 2007 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2007 CS Q30 (2 marks, Multiple choice) – Over 0, 1, 2, L=\0i21i i0\ is
  2. GATE 2007 CS Q78 (2 marks, Multiple choice) – CFG has nonterminals S, A, B, terminals a, b, start S, rules S aB bA, B b bS aBB, A a aS bAA. Which string is generated?
  3. GATE 2007 CS Q79 (2 marks, Multiple choice) – CFG has nonterminals S, A, B, terminals a, b, start S, rules S aB bA, B b bS aBB, A a aS bAA. For the correct string in Q78, how many derivation trees…
  4. GATE 2008 CS Q50 (2 marks, Multiple choice) – Which statements are true? I. Every left-recursive grammar can be converted to right-recursive and vice versa. II. All ε-productions can be removed…
  5. GATE 2008 CS Q51 (2 marks, Multiple choice) – Match E: declarations precede identifier use; F: formal and actual parameter counts agree; G: arithmetic expressions with matched parentheses; H:…
  6. GATE 2009 CS Q12 (1 mark, Multiple choice) – The grammar S aSa bSb a b generates which language over a, b?
  7. GATE 2009 CS Q16 (1 mark, Multiple choice) – Which one of the following is FALSE?
  8. GATE 2021 CS (CS2) Q22 (1 mark, Multiple select) – L1 is regular and L2 is context-free. Which are necessarily context-free?
  9. GATE 2021 CS (CS2) Q51 (2 marks, Multiple select) – For binary strings, wR is reversal. Which languages are context-free? w,x may be empty.
  10. GATE 2015 CS (CS3) Q44 (2 marks, Multiple choice) – Which languages are context-free? L 1=\ambnanbm:m,n1\; L 2=\ambnambn:m,n1\; L 3=\ambn:m=2n+1\.
  11. GATE 2010 CS Q50 (2 marks, Multiple choice) – For nonnegative i,j, let L 1=\0i1j:i j\, L 2=\0i1j:i=j\, L 3=\0i1j:i=2j+1\ and L 4=\0i1j:i2j\. Which is true?
  12. GATE 2017 CS (CS2) Q26 (1 mark, Multiple choice) – With start S and rules S→XY, X→aX a, Y→aYb ε, identify the language.
  13. GATE 2014 CS (CS3) Q46 (2 marks, Multiple choice) – Over =\0,1,c\, let L 1=\0n1n:n0\, L 2=\wcwr:w\0,1\*\, L 3=\wwr:w\0,1\*\, where wr reverses w. Which languages are deterministic context-free?
  14. GATE 2017 CS (CS1) 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…
  15. GATE 2017 CS (CS1) 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?
  16. GATE 2017 CS (CS1) 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…
  17. GATE 2016 CS (CS1) Q26 (1 mark, Multiple choice) – Which of the following languages is generated by the given grammar? S aS bS
  18. GATE 2016 CS (CS1) 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…
  19. GATE 2016 CS (CS1) 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…
  20. GATE 2015 CS (CS1) 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…
  21. 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,\…
  22. GATE 2019 CS Q41 (2 marks, Multiple choice) – Which one of the following languages over =\a,b\ is NOT context-free?
  23. GATE 2026 CS (CS2) Q29 (1 mark, Multiple select) – Which of the following grammars is/are ambiguous?
  24. 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?
  25. 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?
  26. 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…
  27. 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…
  28. 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.…
  29. 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…
  30. 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…
  31. 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…
  32. GATE 2021 CS (CS1) 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…