Subject analysis · 2017–2026
Theory of Computation (TOC)
Every GATE CS question on Theory of Computation (TOC), with how the marks are spread across years and topics.
Questions
77
4 topics
Avg marks / year
12.1
121 marks over 10 years
Peak year
2017
21 marks
Trend
Rising
+20% last 3 yrs
Marks per year
Both shifts counted where there were two · peak highlighted
avg 12.1
21
8
8
9
17
8
9
14
15
12
'17'18'19'20'21'22'23'24'25'26
Topic share
Share of Theory of Computation (TOC)'s 121 marks
4
topics
- Regular Expressions & Finite Automata33%
- Regular and Context-Free Languages & Pumping Lemma33%
- Context-Free Grammars & Push-Down Automata18%
- Turing Machines & Undecidability16%
Topic × year heatmap
Marks from each topic in each year — darker is heavier. Topics that light up every column are the safest bets.
| '17 | '18 | '19 | '20 | '21 | '22 | '23 | '24 | '25 | '26 | |
|---|---|---|---|---|---|---|---|---|---|---|
| Regular Expressions & Finite Automata | 4 | 3 | 2 | 3 | 6 | 1 | 4 | 9 | 5 | 3 |
| Regular and Context-Free Languages & Pumping Lemma | 7 | 2 | 4 | 4 | 6 | 4 | 1 | 1 | 7 | 4 |
| Context-Free Grammars & Push-Down Automata | 6 | 2 | 4 | 4 | 2 | 4 | ||||
| Turing Machines & Undecidability | 4 | 3 | 2 | 2 | 3 | 3 | 1 | 1 |
All 77 Theory of Computation (TOC) questions
2026 8 questions · 12 marks
- FN · Q25Consider 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?Context-Free Grammars & Push-Down Automata · MSQ · 1 mark
- FN · Q26Let M be a non-deterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the…Regular Expressions & Finite Automata · MSQ · 1 mark
- FN · Q51Let L 1 and L 2 be two languages over a finite alphabet, such that L 1 L 2 and L 2 are regular languages. Which of the following statements is/are always true?Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
- FN · Q52Consider the following context-free grammar G : S abaaBAbba A aaBBAb bBabaa B aBb ab In the above grammar, S is the start symbol, a and b are terminal symbols,…Context-Free Grammars & Push-Down Automata · MSQ · 2 marks
- AN · Q13Which one of the following statements is equivalent to the following assertion? Turing machine M decides the language L \ 0, 1\ .Turing Machines & Undecidability · MCQ · 1 mark
- AN · Q29Which of the following grammars is/are ambiguous?Context-Free Grammars & Push-Down Automata · MSQ · 1 mark
- AN · Q47Consider the following two finite automata D 1 and D 2 . Which of the following statements is/are true?Regular Expressions & Finite Automata · MSQ · 2 marks
- AN · Q48Let = \ a, b, c, d\ and let L = \ a i b j c k d l i, j, k, l 0\ . Which of the following constraints ensure(s) that the language L is context-free?Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
2025 10 questions · 15 marks
- FN · Q19Consider 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,…Context-Free Grammars & Push-Down Automata · MCQ · 1 mark
- FN · Q28A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?Regular Expressions & Finite Automata · MSQ · 1 mark
- FN · Q44Consider the following two languages over the alphabet \ a, b\ : L 1 = \ \ a, b\ + AND \ a, b\ +\ L 2 = \ \ a\ + AND \ a, b\ +\ Which ONE of the following stat…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q45Consider the following two languages over the alphabet \ a, b, c\ , where m and n are natural numbers. L 1 = \ a m b m c m + n m, n 1\ L 2 = \ a m b n c m + n…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q50Consider the following deterministic finite automaton (DFA) defined over the alphabet, = \ a, b\ . Identify which of the following language(s) is/are accepted…Regular Expressions & Finite Automata · MSQ · 2 marks
- AN · Q24Which ONE of the following languages is accepted by a deterministic pushdown automaton?Context-Free Grammars & Push-Down Automata · MCQ · 1 mark
- AN · Q25Let G 1 , G 2 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 th…Turing Machines & Undecidability · MCQ · 1 mark
- AN · Q30Consider 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 un…Regular and Context-Free Languages & Pumping Lemma · MSQ · 1 mark
- AN · Q52Let = \ 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…Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
- AN · Q60Let = \ 1, 2, 3, 4\ . For x , let prod (x) be the product of symbols in x modulo 7. We take prod ( ) = 1 , where is the null string. For example, prod (124) =…Regular Expressions & Finite Automata · NAT · 2 marks
2024 8 questions · 14 marks
- FN · Q23Let L 1, L 2 be two regular languages and L 3 a language which is not regular. Which of the following statements is/are always TRUE?Regular and Context-Free Languages & Pumping Lemma · MSQ · 1 mark
- FN · Q50Consider the 5-state DFA M accepting the language L(M) (0 + 1) shown below. For any string w (0 + 1) let n 0(w) be the number of 0's in w and n 1(w) be the num…Regular Expressions & Finite Automata · MSQ · 2 marks
- FN · Q59Let 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…Context-Free Grammars & Push-Down Automata · NAT · 2 marks
- FN · Q61Consider 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,…Regular Expressions & Finite Automata · NAT · 2 marks
- AN · Q22Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?Regular Expressions & Finite Automata · MCQ · 1 mark
- AN · Q41Let M be the 5-state NFA with -transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by M ?Regular Expressions & Finite Automata · MCQ · 2 marks
- AN · Q52Consider a context-free grammar G with the following 3 rules. S aS S aSbS S c Let w L(G) . Let n a(w), n b(w), n c(w) denote the number of times a, b, c occur…Context-Free Grammars & Push-Down Automata · MSQ · 2 marks
- AN · Q62Let L 1 be the language represented by the regular expression b ab (ab ab ) and L 2 = \ w (a + b) w 4\ , where w denotes the length of string w . The number of…Regular Expressions & Finite Automata · NAT · 2 marks
2023 6 questions · 9 marks
- FN · Q14Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet \ 0, 1\ , and has the set of states \ s, p, q, r\ , with s…Regular Expressions & Finite Automata · MCQ · 1 mark
- FN · Q19Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions: letter [A – Za – a] di…Regular Expressions & Finite Automata · MCQ · 1 mark
- FN · Q24Which of the following statements is/are CORRECT?Regular and Context-Free Languages & Pumping Lemma · MSQ · 1 mark
- FN · Q39Consider 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…Context-Free Grammars & Push-Down Automata · MCQ · 2 marks
- FN · Q40Consider 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…Context-Free Grammars & Push-Down Automata · MCQ · 2 marks
- FN · Q63Consider 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 sta…Regular Expressions & Finite Automata · NAT · 2 marks
2022 5 questions · 8 marks
- FN · Q12Which one of the following regular expressions correctly represents the language of the finite automaton given below?Regular Expressions & Finite Automata · MCQ · 1 mark
- FN · Q23Which of the following statements is/are TRUE?Turing Machines & Undecidability · MSQ · 1 mark
- FN · Q46Which of the following is/are undecidable?Turing Machines & Undecidability · MSQ · 2 marks
- FN · Q47Consider the following languages: L 1 = \ a n wa n w \ a, b\ \ L 2 = \ wxw R w, x \ a, b\ , w , x > 0\ Note that w R is the reversal of the string w. Which of…Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
- FN · Q48Consider the following languages: L 1 = \ ww w \ a, b\ \ L 2 = \ a n b n c m m, n 0\ L 3 = \ a m b n c n m, n 0\ Which of the following statements is/are FALSE?Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
2021 11 questions · 17 marks
- FN · Q11Suppose that L 1 is a regular language and L 2 is a context-free language. Which one of the following languages is NOT necessarily context-free?Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- FN · Q22Let M denote an encoding of an automaton M. Suppose that = \ 0, 1\ . Which of the following languages is/are NOT recursive?Turing Machines & Undecidability · MSQ · 1 mark
- FN · Q48Consider the following language: L = \ w \ 0,1\ w ends with the substring 011 \ Which one of the following deterministic finite automata accepts L?Regular Expressions & Finite Automata · MCQ · 2 marks
- FN · Q49For a Turing machine M, M denotes an encoding of M. Consider the following two languages: L 1 = \ M M takes more than 2021 steps on all inputs \ L 2 = \ M M ta…Turing Machines & Undecidability · MCQ · 2 marks
- FN · Q61In a pushdown automaton P = (Q, , , , q 0, F), a transition of the form, where p, q Q, a \ \ , and X, Y \ \ , represents (q, Y) (p, a, X) Consider the followin…Context-Free Grammars & Push-Down Automata · NAT · 2 marks
- AN · Q19Let L \ 0, 1\ be an arbitrary regular language accepted by a minimal DFA with k states. Which one of the following languages must necessarily be accepted by a…Regular Expressions & Finite Automata · MCQ · 1 mark
- AN · Q22Let L 1 be a regular language and L 2 be a context-free language. Which of the following languages is/are context-free?Regular and Context-Free Languages & Pumping Lemma · MSQ · 1 mark
- AN · Q27Consider the following deterministic finite automation (DFA). The number of strings of length 8 accepted by the above automation is .Regular Expressions & Finite Automata · NAT · 1 mark
- AN · Q46Consider the following two statements about regular languages: S 1 : Every infinite regular language contains an undecidable language as a subset. S 2 : Every…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- AN · Q51For a string w, we define w R to be the reverse of w. For example, if w = 01101 then w R = 10110. Which of the following languages is/are context-free?Regular and Context-Free Languages & Pumping Lemma · MSQ · 2 marks
- AN · Q57Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string is divisible by three.Regular Expressions & Finite Automata · MSQ · 2 marks
2020 6 questions · 9 marks
- FN · Q17Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?Regular Expressions & Finite Automata · MCQ · 1 mark
- FN · Q18Consider the following statements: I. If L 1 L 2 is regular, then both L 1 and L 2 must be regular. II. The class of regular languages is closed under infinite…Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- FN · Q20Consider the language L = \ a n n 0\ \ a nb n n 0\ and the following statements. I. L is deterministic context-free. II. L is context-free but not deterministi…Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- FN · Q36Which of the following languages are undecidable? Note that M indicates encoding of the Turing machine M. L 1 = \ M L(M) = \ L 2 = \ M, w, q M on input w reach…Turing Machines & Undecidability · MCQ · 2 marks
- FN · Q42Consider the following languages. L 1 = \ wxyx w, x, y (0 + 1) +\ L 2 = \ xy x, y (a + b) , x = y , x y\ Which one of the following is TRUE?Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q61Consider 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 accep…Regular Expressions & Finite Automata · NAT · 2 marks
2019 5 questions · 8 marks
- FN · Q17If L is a regular language over = \ a, b\ , which one of the following languages is NOT regular?Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- FN · Q25For = \ a, b\ , let us consider the regular language L = \ x x = a 2+3k or x = b 10+12k , k 0\ . Which one of the following can be a pumping length (the consta…Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- FN · Q41Which one of the following languages over = \ a, b\ is NOT context-free?Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q44Consider the following sets: S 1 : Set of all recursively enumerable languages over the alphabet \ 0, 1\ . S 2 : Set of all syntactically valid C programs. S 3…Turing Machines & Undecidability · MCQ · 2 marks
- FN · Q58Let be the set of all bijections from \ 1, ..., 5\ to \ 1, ..., 5\ , where id denotes the identity function, i.e. id(j) = j, j . Let denote composition on func…Regular Expressions & Finite Automata · NAT · 2 marks
2018 5 questions · 8 marks
- FN · Q16Let 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?Regular Expressions & Finite Automata · MCQ · 1 mark
- FN · Q17The set of all recursively enumerable languages isTuring Machines & Undecidability · MCQ · 1 mark
- FN · Q45Consider the following languages: I. \ a m b n c p d q m + p = n + q, where m, n, p, q 0\ II. \ a m b n c p d q m = n and p = q, where m, n, p, q 0\ III. \ a m…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q46Consider 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…Turing Machines & Undecidability · MCQ · 2 marks
- FN · Q62Given a language L, define L i as follows: L 0 = \ \ L i = L i-1 L for all i > 0 The order of a language L is defined as the smallest k such that L k = L k+1 .…Regular Expressions & Finite Automata · NAT · 2 marks
2017 13 questions · 21 marks
- FN · Q10Consider 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 represent…Context-Free Grammars & Push-Down Automata · MCQ · 1 mark
- FN · Q22Consider 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 f…Regular Expressions & Finite Automata · NAT · 1 mark
- FN · Q34If 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?Context-Free Grammars & Push-Down Automata · MCQ · 2 marks
- FN · Q37Consider 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 language L(…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q38Consider the following languages over the alphabet = \ a, b, c\ . Let L 1 = \ a n b n c m m, n 0\ and L 2 = \ a m b n c n m, n 0\ . Which of the following are…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- FN · Q39Let 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 Turi…Turing Machines & Undecidability · MCQ · 2 marks
- FN · Q43Consider the following grammar: stmt if expr then expr else expr ; stmt 0 expr term relop term term term id number id a b c number [0-9] where relop is a relat…Context-Free Grammars & Push-Down Automata · NAT · 2 marks
- AN · Q4Let L 1, L 2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? I. L 1 L 2 is context-free. II. L 1 i…Regular and Context-Free Languages & Pumping Lemma · MCQ · 1 mark
- AN · Q16Identify the language generated by the following grammar, where S is the start variable. S XY X aX a Y aYbContext-Free Grammars & Push-Down Automata · MCQ · 1 mark
- AN · Q25The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = \ w 1 a w 2 w 1, w 2 \ a, b\ , w 1 = 2, w 2 3\…Regular Expressions & Finite Automata · NAT · 1 mark
- AN · Q39Let denote the transition function and denote the extended transition function of the -NFA whose transition table is given below: The (q 2, aba) isRegular Expressions & Finite Automata · MCQ · 2 marks
- AN · Q40Consider the following languages. L 1 = \ a p p is a prime number \ L 2 = \ a n b m c 2m n 0, m 0\ L 3 = \ a n b n c 2n n 0\ L 4 = \ a n b n n 1\ Which of the…Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
- AN · Q41Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted…Turing Machines & Undecidability · MCQ · 2 marks

