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.

Practise Theory of Computation (TOC)

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

Rising +20%
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 Automata4323614953
Regular and Context-Free Languages & Pumping Lemma7244641174
Context-Free Grammars & Push-Down Automata624424
Turing Machines & Undecidability43223311
Recommended book · affiliate linkIntroduction to Automata Theory (Hopcroft & Ullman)Regular languages, CFGs, pushdown automata and Turing machines.

All 77 Theory of Computation (TOC) questions

2026 8 questions · 12 marks
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. AN · Q29Which of the following grammars is/are ambiguous?Context-Free Grammars & Push-Down Automata · MSQ · 1 mark
  7. 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
  8. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. AN · Q24Which ONE of the following languages is accepted by a deterministic pushdown automaton?Context-Free Grammars & Push-Down Automata · MCQ · 1 mark
  7. 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
  8. 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
  9. 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
  10. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  1. 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
  2. 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
  3. FN · Q24Which of the following statements is/are CORRECT?Regular and Context-Free Languages & Pumping Lemma · MSQ · 1 mark
  4. 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
  5. 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
  6. 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
  1. 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
  2. FN · Q23Which of the following statements is/are TRUE?Turing Machines & Undecidability · MSQ · 1 mark
  3. FN · Q46Which of the following is/are undecidable?Turing Machines & Undecidability · MSQ · 2 marks
  4. 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
  5. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  1. 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
  2. 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
  3. FN · Q41Which one of the following languages over = \ a, b\ is NOT context-free?Regular and Context-Free Languages & Pumping Lemma · MCQ · 2 marks
  4. 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
  5. 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
  1. 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
  2. FN · Q17The set of all recursively enumerable languages isTuring Machines & Undecidability · MCQ · 1 mark
  3. 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
  4. 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
  5. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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