The GATE Grind

GATE Theory of Computation: Regular Expressions and Finite Automata – Previous Year Questions

52 GATE previous year questions on Regular Expressions and Finite Automata (Theory of Computation, Computer Science) with answers and explanations, from every paper.

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

  1. GATE 2007 CS Q29 (2 marks, Multiple choice) – What is the minimum DFA size for binary strings whose number of0s is divisible by3 and number of1s divisible by5?
  2. GATE 2007 CS Q74 (2 marks, Multiple choice) – Which regular expression gives the language of the automaton shown?
  3. GATE 2007 CS Q75 (2 marks, Multiple choice) – How many states does the minimum automaton equivalent to the shown FSA have?
  4. GATE 2008 CS Q49 (2 marks, MTA) – Automata Y, Z have start1 and final2. Y transitions: 1:a→1, b→2; 2:a→2, b→1. Z:1:a→2, b→2;2:a→1, b→1. Which table is their product Z×Y? P starts, R is…
  5. GATE 2008 CS Q52 (2 marks, Multiple choice) – Match the shown NFAs P, Q, R, S with regular expressions: 1. +0(01*1+00)*01*; 2. +0(10*1+00)*0; 3. +0(10*1+10)*1; 4. +0(10*1+10)*10*.
  6. GATE 2009 CS Q15 (1 mark, Multiple choice) – Which language over 0, 1 is described by (0+1)*0(0+1)*0(0+1)*?
  7. GATE 2009 CS Q41 (2 marks, Multiple choice) – The DFA shown accepts all strings over 0, 1 that
  8. GATE 2021 CS (CS2) Q19 (1 mark, Multiple choice) – Regular L⊆0,1* has a minimal DFA with k states. Which language necessarily also has a minimal DFA with k states?
  9. GATE 2021 CS (CS2) Q27 (1 mark, Numerical answer) – For the DFA shown, how many binary strings of length eight are accepted?
  10. GATE 2021 CS (CS2) Q57 (2 marks, Multiple select) – Which regular expressions denote the binary numbers divisible by three? Leading zeros are allowed and ε is treated as divisible by three. Here + means…
  11. GATE 2015 CS (CS3) Q32 (1 mark, Multiple choice) – Over Σ=0,1, let L be represented by Σ*0011Σ*. Find the minimum DFA-state count for its complement.
  12. GATE 2015 CS (CS2) Q45 (2 marks, Numerical answer) – Find the number of states in the minimal DFA for (0+1)*(10).
  13. GATE 2015 CS (CS2) Q60 (2 marks, Multiple choice) – Over 0,1, λ denotes the empty string. A regular grammar satisfies X0=1X1, X1=0X1+1X2, X2=0X1+λ. Which expression denotes X0?
  14. GATE 2010 CS Q49 (2 marks, Multiple choice) – Which regular expression denotes all binary strings with an even number of ones?
  15. GATE 2010 CS Q51 (2 marks, Multiple choice) – Let w be any binary string of length n, and L the set of all its substrings. What is the minimum number of states in an NFA accepting L?
  16. GATE 2011 CS Q52 (2 marks, Multiple choice) – Over alphabet a, L=\ank:k>0\, with fixed positive integer n. Find the smallest DFA state count.
  17. GATE 2011 CS Q55 (2 marks, Multiple choice) – DFA D has transitions p:a→s,b→q; q:a→t,b→r; r loops on a,b; s,t are accepting and each loops on a,b. Which displayed DFA is an equivalent minimal…
  18. GATE 2013 CS Q18 (1 mark, Multiple choice) – L₁=∅ and L₂=a. Evaluate L 1L 2* L 1*.
  19. GATE 2013 CS Q43 (2 marks, Multiple choice) – For the shown DFA A, which are false? 1: Its language complement is context-free. 2: L(A)=L((11*0+0)(0+1)*0*1*). 3: A is minimal. 4: A accepts all…
  20. GATE 2012 CS Q22 (1 mark, Multiple choice) – Over alphabet a, with ε the empty string, find the complement of the language accepted by the shown NFA.
  21. GATE 2012 CS Q35 (1 mark, Multiple choice) – L=ab,aa,baa. Which strings belong to L*? 1: abaabaaabaa; 2: aaaabaaaa; 3: baaaaabaaaab; 4: baaaaabaa.
  22. GATE 2012 CS Q56 (2 marks, Multiple choice) – Over 0,1, every three-symbol substring must contain at most two zeros; all words shorter than three are included. The partial DFA is shown. Which…
  23. GATE 2017 CS (CS2) Q35 (1 mark, Numerical answer) – Find the minimum number of DFA states for L=\w 1aw 2:w 1,w 2\a,b\*,\ w 1 =2,\ w 2 3\.
  24. GATE 2017 CS (CS2) Q49 (2 marks, Multiple choice) – An ε-NFA has start q₀. Transition triples (ε,a,b) are q₀:(q₂,q₁,q₀); q₁:(q₂,q₂,q₃); q₂:(q₀,∅,∅); q₃:(∅,∅,q₂). Find the extended transition δ̂(q₂,aba).
  25. GATE 2016 CS (CS2) Q26 (1 mark, Numerical answer) – How many states are in a smallest DFA for (0+1)*(0+1)(0+1)*?
  26. GATE 2016 CS (CS2) Q52 (2 marks, Multiple choice) – I: If every NFA state is accepting, the accepted language is Σ*. II: There exists a regular language A such that A∩B is regular for every language B.…
  27. GATE 2014 CS (CS3) Q25 (1 mark, Numerical answer) – Over =\a,b\, find the length of the shortest string NOT in the language of a*b*(ba)*a*.
  28. GATE 2014 CS (CS1) Q26 (1 mark, Multiple choice) – For the finite automaton shown, find the set of reachable states after input 0011.
  29. GATE 2014 CS (CS1) Q46 (2 marks, Multiple choice) – Which regular expressions represent the shown DFA? I: 0*1(1+00*1)*; II: 0*1*1+11*0*1; III: (0+1)*1.
  30. GATE 2017 CS (CS1) Q32 (1 mark, Numerical answer) – 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…
  31. GATE 2016 CS (CS1) Q28 (1 mark, Multiple choice) – Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive…
  32. GATE 2015 CS (CS1) Q49 (2 marks, Numerical answer) – [Two DFAs, each with two states. DFA M: the start state loops on b, reads a to move to the final state, the final state loops on a and reads b to…
  33. GATE 2018 CS Q16 (1 mark, Multiple choice) – 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…
  34. GATE 2018 CS Q62 (2 marks, Numerical answer) – Given a language L, define Li as follows: L0=\\ and Li=Li-1 L for all i>0. The order of a language L is defined as the smallest k such that Lk=Lk+1.…
  35. GATE 2019 CS Q58 (2 marks, Numerical answer) – Let 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 functions.…
  36. GATE 2026 CS (CS2) Q47 (2 marks, Multiple select) – Consider the following two finite automata D 1 and D 2. Which of the following statements is/are true?
  37. GATE 2026 CS (CS1) Q26 (1 mark, Multiple select) – Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states…
  38. GATE 2026 CS (CS1) Q51 (2 marks, Multiple select) – Let 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…
  39. GATE 2025 CS (CS2) Q60 (2 marks, Numerical answer) – Let = \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) =…
  40. GATE 2025 CS (CS1) Q28 (1 mark, Multiple select) – A regular language L is accepted by a non-deterministic finite automaton (NFA) with n states. Which of the following statement(s) is/are FALSE?
  41. GATE 2025 CS (CS1) Q50 (2 marks, Multiple select) – Consider the following deterministic finite automaton (DFA) defined over the alphabet, = \a,b\. Identify which of the following language(s) is/are…
  42. GATE 2024 CS (CS2) Q22 (1 mark, Multiple choice) – Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? (Two states: start state q0…
  43. GATE 2024 CS (CS2) Q41 (2 marks, Multiple choice) – Let M be the 5-state NFA with -transitions shown: start state 1 with ε to 2 and ε to 4; state 2 (accepting) goes 0 to 3; state 3 goes 0 to 2 and ε to…
  44. GATE 2024 CS (CS2) Q62 (2 marks, Numerical answer) – Let 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…
  45. GATE 2024 CS (CS1) Q50 (2 marks, Multiple select) – Consider the 5-state DFA M accepting the language L(M)(0+1)* shown in the figure (start/accepting state 1; 1-0->2, 2-0->3, 3-0->1, 2-1->1, 3-1->2,…
  46. GATE 2024 CS (CS1) Q61 (2 marks, Numerical answer) – Consider the two regular expressions over the alphabet \0,1\: r=0*+1* and s=01*+10*. The total number of strings of length less than or equal to 5,…
  47. GATE 2023 CS Q14 (1 mark, Multiple choice) – Consider 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…
  48. GATE 2023 CS Q63 (2 marks, Numerical answer) – 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…
  49. GATE 2022 CS Q12 (1 mark, Multiple choice) – Which one of the following regular expressions correctly represents the language of the finite automaton given below?
  50. GATE 2021 CS (CS1) Q48 (2 marks, Multiple choice) – Consider the following language. L = \w \0,1\* w ends with the substring 011\ Which one of the following deterministic finite automata accepts L?
  51. GATE 2020 CS Q17 (1 mark, MTA) – Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
  52. GATE 2020 CS Q61 (2 marks, Numerical answer) – 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…