# Finite Automata and Regular Language · Theory of Computation · GATE CSE

Start Practice

## Marks 1

GATE CSE 2024 Set 2
Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?...
GATE CSE 2024 Set 1
Let $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?
GATE CSE 2022
Which one of the following regular expressions correctly represents the language of the finite automation given below? ...
GATE CSE 2020
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
GATE CSE 2020
Consider the following statements. I. If L1 $$\cup$$ L2 is regular, then both L1 and L2 must be regular. II. The class of regular languages is close...
GATE CSE 2019
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
GATE CSE 2019
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 (th...
GATE CSE 2016 Set 2
The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $${\left( {0 + 1} \right)^ * }\left( {... GATE CSE 2016 Set 2 Language$${L_1}$$is defined by the grammar:$$S{}_1 \to a{S_1}b|\varepsilon $$Language$${L_2}$$is defined by the grammar:$$S{}_2 \to ab{S_2}|\va...
GATE CSE 2016 Set 1
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $$0s$$ and two consecutiv...
GATE CSE 2015 Set 3
Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } }$$ where $$\sum { = \left\{ {0,1} \right\}} .$$ What is ...
GATE CSE 2014 Set 1
Which one of the following is TRUE?
GATE CSE 2014 Set 1
Consider the finite automation in the following figure. What is the set of reachable states for the input string $$0011?$$...
GATE CSE 2014 Set 3
The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}}$$) of the following regular expression is ________...
GATE CSE 2014 Set 2
If $${L_1} = \left\{ {{a^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$ and $${L_2} = \left\{ {{b^n}\left| {n \ge \left. 0 \right\}} \right.} \... GATE CSE 2013 Consider the languages$${L_1} = \phi $$and$${L_2} = \left\{ a \right\}.$$Which one of the following represents$${L_1}\,L_2^ * UL_1^ * ?$$GATE CSE 2012 What is the complement of the language accepted by the$$NFA$$shown below? Assume$$\sum { = \left\{ a \right\}\,\,} $$and$$\varepsilon $$is the ... GATE CSE 2010 Let$${L_1}$$recursive language. Let$${L_2}$$and$${L_3}$$be languages that are recursively enumerable but not recursive. Which of the following s... GATE CSE 2009 Which one of the following languages over the alphabet$$\left\{ {0,\left. 1 \right)} \right.$$is described by the regular expression$${\left( {0 + ...
GATE CSE 2003
The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ *$$denotes the same set as
GATE CSE 2003
Consider the set $$\sum {^ * }$$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum {^ * } }$$ with the concatena...
GATE CSE 2001
Consider the following two statements; $${S_1}\,\,:\,\,\left\{ {{0^{2n}}\left| {n \ge 1} \right.} \right\}$$ is a regular language $${S_2}\,\,:\,\,\le... GATE CSE 2001 Given an arbitrary non-deterministic finite automaton$$(NFA)$$with$$N$$states, the maximum number of states in an equivalent minimized$$DFA$$is ... GATE CSE 2000 Let$$S$$and$$T$$be languages over$$\sum { = \left\{ {a,b} \right\}} $$represented by the regular expressions$${\left( {a + {b^ * }} \right)^ * ...
GATE CSE 2000
Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is true?
GATE CSE 1999
Consider the regular expression $$(0+1)(0+1).......n$$ times. The minimum state finite automation that recognizes the language represented by this reg...
GATE CSE 1998
If the regular set $$A$$ is represented by $$A = {\left( {01 + 1} \right)^ * }$$ and the regular set $$'B'$$ is represented by $$B = \left( {{{\left( ... GATE CSE 1998 Which of the following sets can be recognized by a Deterministic Finite-state Automation? GATE CSE 1998 The string$$1101$$does not belong to the set represented by GATE CSE 1998 How many substrings of different lengths (non-zero) can be formed from a character string of length$$n$$? GATE CSE 1997$$\sum { = \left\{ {a,b} \right\},\,\,} $$which one of the following sets is not countable. GATE CSE 1996 Which two of the following four regular expressions are equivalent? (i)$${\left( {00} \right)^ * }\left( {\varepsilon + 0} \right)$$(ii)$${\left(...
GATE CSE 1996
Let $$L \subseteq \sum {^{^ * }\,}$$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,}$$ which of the following is true?
GATE CSE 1994
State True or False with one line explanation: A FSM (Finite State Machine) can be designed to add two integers of any arbitrary length (arbitrary num...

## Marks 2

GATE CSE 2024 Set 2
Let M be the 5-state NFA with ε-transitions shown in the diagram below. Which one of the following regular expressions represents the language accepte...
GATE CSE 2024 Set 2
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 strin...
GATE CSE 2024 Set 1
Consider the 5-state DFA $M$ accepting the language $L(M) \subseteq (0+1)^*$ shown below. For any string $w \in (0+1)^*$ let $n_0(w)$ be the number of...
GATE CSE 2024 Set 1
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 ...
GATE CSE 2023
EXAM MAP
Medical
NEET