GATE Theory of Computation: Regular Expressions and Finite Automata – Previous Year Questions
23 GATE previous year questions on Regular Expressions and Finite Automata (Theory of Computation, Computer Science) with answers and explanations, from every paper.
- GATE 2017 CS Q32 – 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…
- GATE 2016 CS Q28 – Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive…
- GATE 2015 CS Q49 – [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…
- GATE 2018 CS Q16 – 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…
- GATE 2018 CS Q62 – 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.…
- GATE 2019 CS Q58 – 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.…
- GATE 2026 CS (CS2) Q47 – Consider the following two finite automata D 1 and D 2. Which of the following statements is/are true?
- GATE 2026 CS (CS1) Q26 – 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…
- GATE 2026 CS (CS1) Q51 – 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…
- GATE 2025 CS (CS2) Q60 – 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) =…
- GATE 2025 CS (CS1) Q28 – 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?
- GATE 2025 CS (CS1) Q50 – Consider the following deterministic finite automaton (DFA) defined over the alphabet, = \a,b\. Identify which of the following language(s) is/are…
- GATE 2024 CS (CS2) Q22 – Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? (Two states: start state q0…
- GATE 2024 CS (CS2) Q41 – 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…
- GATE 2024 CS (CS2) Q62 – 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…
- GATE 2024 CS (CS1) Q50 – 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,…
- GATE 2024 CS (CS1) Q61 – 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,…
- GATE 2023 CS Q14 – 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…
- GATE 2023 CS Q63 – 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…
- GATE 2022 CS Q12 – Which one of the following regular expressions correctly represents the language of the finite automaton given below?
- GATE 2021 CS Q48 – Consider the following language. L = \w \0,1\* w ends with the substring 011\ Which one of the following deterministic finite automata accepts L?
- GATE 2020 CS Q17 – Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
- GATE 2020 CS Q61 – 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…