53 real GATE CSE questions from 2012 to 2025, with the official answer key and a worked solution for each. Filter by year, topic, type, marks or keyword.
Questions belong to the GATE organising institutes; this copy is for personal study. Coverage varies by year: questions that need a figure I could not read, or whose answer I could not verify, were left out.
Showing 53 of 53 questions · 0 correct of 0 attempted · marks 0 / 80
GATE 2025 CS1 · Q19MCQ1 markContext-Free Grammars & Languages
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 variable, and the rules of G are described as: S → aaB | Abb, A → a | aA, B → b | bB. Which ONE of the languages L(G) is accepted by G?
GATE 2025 CS2 · Q24MCQ1 markPushdown Automata
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
Let G1, G2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is decidable?
Consider the two lists List I and List II given below. List I: (i) Context free languages, (ii) Recursive languages, (iii) Regular languages. List II: (a) Closed under union, (b) Not closed under complementation, (c) Closed under intersection. For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS1 · Q44MCQ2 marksRegular Expressions & Regular Languages
Consider the following two languages over the alphabet {a, b}: L1 = { αβα | α ∈ {a, b}+ AND β ∈ {a, b}+ } and L2 = { αβα | α ∈ {a}+ AND β ∈ {a, b}+ }. Which ONE of the following statements is CORRECT?
GATE 2025 CS1 · Q45MCQ2 marksContext-Free Grammars & Languages
Consider the following two languages over the alphabet {a, b, c}, where m and n are natural numbers. L1 = { ambmcm+n | m, n ≥ 1 } and L2 = { ambncm+n | m, n ≥ 1 }. Which ONE of the following statements is CORRECT?
GATE 2025 CS2 · Q52MSQ2 marksRegular Expressions & Regular Languages
Let Σ = {a, b, c}. For x ∈ Σ*, and α ∈ Σ, let #α(x) denote the number of occurrences of α in x. Which one or more of the following option(s) define(s) regular language(s)?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS1 · Q23MSQ1 markRegular Expressions & Regular Languages
Let L1, L2 be two regular languages and L3 a language which is not regular. Which of the following statements is/are always TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2024 CS2 · Q52MSQ2 marksContext-Free Grammars & Languages
Consider a context-free grammar G with the following 3 rules. S → aS, S → aSbS, S → c. Let w ∈ L(G). Let na(w), nb(w), nc(w) denote the number of times a, b, c occur in w, respectively. Which of the following statements is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
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 string w = a30b30c30 is derivable from S. The number of steps (application of rules) in the derivation S ⇒* w is ______.
GATE 2024 CS1 · Q61NAT2 marksRegular Expressions & Regular Languages
Consider the following two regular expressions over the alphabet {0,1}: r = 0* + 1*, s = 01* + 10*. The total number of strings of length less than or equal to 5, which are neither in r nor in s, is ______.
GATE 2024 CS2 · Q62NAT2 marksRegular Expressions & Regular Languages
Let L1 be the language represented by the regular expression b*ab*(ab*ab*)* and L2 = { w ∈ (a + b)* | |w| ≤ 4 }, where |w| denotes the length of string w. The number of strings in L2 which are also in L1 is ______.
One or more options may be correct. Select all that apply, then submit.
GATE 2023 · Q39MCQ2 marksContext-Free Grammars & Languages
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 non-terminal is S. Which one of the following statements is CORRECT?
Consider the language L over the alphabet {0, 1}, given below: L = {w ∈ {0, 1}* | w does not contain three or more consecutive 1's}. The minimum number of states in a Deterministic Finite-State Automaton (DFA) for L is ______.
One or more options may be correct. Select all that apply, then submit.
GATE 2022 · Q47MSQ2 marksRegular Expressions & Regular Languages
Consider the following languages: L1 = { an w an | w ∈ {a, b}* } and L2 = { w x wR | w, x ∈ {a, b}*, |w|, |x| > 0 }. Note that wR is the reversal of the string w. Which of the following is/are TRUE?
One or more options may be correct. Select all that apply, then submit.
GATE 2022 · Q48MSQ2 marksContext-Free Grammars & Languages
Consider the following languages: L1 = { ww | w ∈ {a, b}* }, L2 = { anbncm | m, n ≥ 0 }, L3 = { ambncn | m, n ≥ 0 }. Which of the following statements is/are FALSE?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q1MCQ1 markContext-Free Grammars & Languages
Suppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily context-free?
GATE 2021 Set 1 · Q12MSQ1 markDecidability & Undecidability
Let ⟨M⟩ denote an encoding of an automaton M. Suppose that Σ = {0, 1}. Which of the following languages is/are NOT recursive?
One or more options may be correct. Select all that apply, then submit.
GATE 2021 Set 1 · Q39MCQ2 marksDecidability & Undecidability
For a Turing machine M, ⟨M⟩ denotes an encoding of M. Consider the following two languages. L1 = { ⟨M⟩ | M takes more than 2021 steps on all inputs } and L2 = { ⟨M⟩ | M takes more than 2021 steps on some input }. Which one of the following options is correct?
GATE 2020 · Q7MCQ1 markRegular Expressions & Regular Languages
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
GATE 2020 · Q8MCQ1 markRegular Expressions & Regular Languages
Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is closed under infinite union. Which of the above statements is/are TRUE?
GATE 2020 · Q10MCQ1 markPushdown Automata
Consider the language L = { an | n ≥ 0 } ∪ { anbn | n ≥ 0 } and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministic context-free. III. L is not LL(k) for any k. Which of the above statements is/are TRUE?
Which of the following languages are undecidable? Note that ⟨M⟩ indicates encoding of the Turing machine M. L1 = { ⟨M⟩ | L(M) = ∞ }, L2 = { ⟨M, w, q⟩ | M on input w reaches state q in exactly 100 steps }, L3 = { ⟨M⟩ | L(M) is not recursive }, L4 = { ⟨M⟩ | L(M) contains at least 21 members }.
Consider the following language: L = { x ∈ {a, b}* | number of a's in x is divisible by 2 but not divisible by 3 }. The minimum number of states in a DFA that accepts L is ______.
GATE 2019 Set 2 · Q7MCQ1 markRegular Expressions & Regular Languages
If L is a regular language over Σ = {a, b}, which one of the following languages is NOT regular?
GATE 2019 Set 2 · Q15MCQ1 markRegular Expressions & Regular Languages
For Σ = {a, b}, let us consider the regular language L = { x | x = a2+3k or x = b10+12k, k ≥ 0 }. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for L?
GATE 2019 Set 2 · Q31MCQ2 marksContext-Free Grammars & Languages
Which one of the following languages over Σ = {a, b} is NOT context-free?
Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0, 1}. S2. Set of all syntactically valid C programs. S3. Set of all languages over the alphabet {0, 1}. S4. Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?
Let N be an NFA with n states. Let k be the number of states of a minimal DFA which is equivalent to N. Which one of the following is necessarily true?
GATE 2018 · Q7MCQ1 markTuring Machines
The set of all recursively enumerable languages is
GATE 2018 · Q35MCQ2 marksContext-Free Grammars & Languages
Consider the following languages: I. { ambncpdq | m + p = n + q, where m, n, p, q ≥ 0 }. II. { ambncpdq | m = n and p = q, where m, n, p, q ≥ 0 }. III. { ambncpdq | m = n = p and p ≠ q, where m, n, p, q ≥ 0 }. IV. { ambncpdq | mn = p + q, where m, n, p, q ≥ 0 }. Which of the languages above are context-free?
Consider the following problems. L(G) denotes the language generated by a grammar G. L(M) denotes the language accepted by a machine M. (I) For an unrestricted grammar G and a string w, whether w ∈ L(G). (II) Given a Turing machine M, whether L(M) is regular. (III) Given two grammars G1 and G2, whether L(G1) = L(G2). (IV) Given an NFA N, whether there is a deterministic PDA P such that N and P accept the same language. Which one of the following statements is correct?
Consider the language L given by the regular expression (a + b)*b(a + b) over the alphabet {a, b}. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is ______.
GATE 2017 Set 1 · Q34MCQ2 marksContext-Free Grammars & Languages
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 Set 1 · Q37MCQ2 marksContext-Free Grammars & Languages
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals. G1: S → aSb | T, T → cT | ε. G2: S → bSa | T, T → cT | ε. The language L(G1) ∩ L(G2) is
GATE 2017 Set 1 · Q38MCQ2 marksContext-Free Grammars & Languages
Consider the following languages over the alphabet Σ = {a, b, c}. Let L1 = { anbncm | m, n ≥ 0 } and L2 = { ambncn | m, n ≥ 0 }. Which of the following are context-free languages? I. L1 ∪ L2 II. L1 ∩ L2
GATE 2017 Set 1 · Q39MCQ2 marksTuring Machines
Let A and B be finite alphabets and let # be a symbol outside both A and B. Let f be a total function from A* to B*. We say f is computable if there exists a Turing machine M which given an input x in A*, always halts with f(x) on its tape. Let Lf denote the language { x # f(x) | x ∈ A* }. Which of the following statements is true:
GATE 2016 Set 1 · Q16MCQ1 markContext-Free Grammars & Languages
Which of the following languages is generated by the given grammar? S → aS | bS | ε
GATE 2016 Set 1 · Q17MCQ1 markDecidability & Undecidability
Which of the following decision problems are undecidable? I. Given NFAs N1 and N2, is L(N1) ∩ L(N2) = Φ? II. Given a CFG G = (N, Σ, P, S) and a string x ∈ Σ*, does x ∈ L(G)? III. Given CFGs G1 and G2, is L(G1) = L(G2)? IV. Given a TM M, is L(M) = Φ?
GATE 2016 Set 1 · Q18MCQ1 markRegular Expressions & Regular Languages
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
GATE 2014 Set 1 · Q15MCQ1 markRegular Expressions & Regular Languages
Which one of the following is TRUE?
GATE 2014 Set 1 · Q35MCQ2 marksTuring Machines
Let L be a language and its complement be denoted L'. Which one of the following is NOT a viable possibility?
GATE 2013 Code A · Q8MCQ1 markRegular Expressions & Regular Languages
Consider the languages L1 = Φ and L2 = {a}. Which one of the following represents L1 L2* ∪ L1*?
GATE 2013 Code A · Q17MCQ1 markTuring Machines
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable languages are closed under union and complementation. 3. Turing decidable languages are closed under intersection and complementation. 4. Turing recognizable languages are closed under union and intersection.
GATE 2013 Code A · Q32MCQ2 marksContext-Free Grammars & Languages
Consider the following languages: L1 = { 0p1q0r | p, q, r ≥ 0 } and L2 = { 0p1q0r | p, q, r ≥ 0, p ≠ r }. Which one of the following statements is FALSE?
Consider the DFA A with three states. The start state q0 goes to q1 on 1 and to q2 on 0. State q1 loops to itself on 1 and goes to q2 on 0. State q2 is the only accepting state and loops to itself on both 0 and 1. Which of the following are FALSE? 1. Complement of L(A) is context-free. 2. L(A) = L((11*0 + 0)(0 + 1)*1*). 3. For the language accepted by A, A is the minimal DFA. 4. A accepts all strings over {0, 1} of length at least 2.
GATE 2013 Code A · Q41MCQ2 marksDecidability & Undecidability
Which of the following is/are undecidable? 1. G is a CFG. Is L(G) = Φ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is the complement of L also context-free? 3) If L is a regular language, then, is the complement of L also regular? 4) If L is a recursive language, then, is the complement of L also recursive?
GATE 2012 Code A · Q25MCQ1 markRegular Expressions & Regular Languages
Given the language L = {ab, aa, baa}, which of the following strings are in L*? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa