# 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

Consider the language L over the alphabet {0, 1}, given below:
$$L = \{ w \in {\{ 0,1\} ^ * }|w$$ does not contain three or more consecutive $$1's\} $...

GATE CSE 2021 Set 1

Consider the following language.
L = { w ∈ {0, 1}* | w ends with the substring 011}
Which one of the following deterministic finite automata ac...

GATE CSE 2020

Consider the following language.
L = {x $$ \in $$ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3}
The minimum number of states ...

GATE CSE 2018

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 follo...

GATE CSE 2018

Given a language $$𝐿,$$ define $${L^i}$$ as follows: $${L^0} = \left\{ \varepsilon \right\}$$
$${L^i} = {L^{i - 1}}.\,\,L$$ for all $$i > 0$$
...

GATE CSE 2016 Set 2

Consider the following two statements:
$$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting states then the language accepte...

GATE CSE 2016 Set 2

Consider the following languages:
$$$\eqalign{
& {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr
& {L_2} = \left\{ {{a^n...

GATE CSE 2016 Set 1

Consider the transition diagram of a $$PDA$$ given below with input alphabet $$\sum {\, = \left\{ {a,b} \right\}} $$ and stack alphabet $$\Gamma = \l...

GATE CSE 2015 Set 1

Consider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is___________....

GATE CSE 2015 Set 1

Consider the NPDA $$\left\langle {Q = \left\{ {{q_0},{q_1},{q_2}} \right\}} \right.,$$ $$\Sigma = \left \{ 0, 1 \right \},$$ $$\Gamma = \left \{ 0, 1,...

GATE CSE 2015 Set 2

The number of states in the minimal deterministic finite automaton corresponding to the regular expression $${\left( {0 + 1} \right)^{\,\, * }}\left( ...

GATE CSE 2015 Set 2

Which of the following languages is/are regular?
$${L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right.$$ and $$\left. {\left| w \ri...

GATE CSE 2015 Set 2

Consider the alphabet $$\sum { = \left\{ {0,1} \right\},} $$ the null/empty string $$\lambda $$ and the sets of strings $${X_0},\,{X_1},$$ and $${X_2}...

GATE CSE 2014 Set 1

Which of the regular expression given below represent the following $$DFA?$$
...

GATE CSE 2014 Set 2

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$...

GATE CSE 2014 Set 2

Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences of $$(110)'s$$ as $$(011)'s$$$$...

GATE CSE 2013

Consider the following languages
$${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$
$${L_2} = \left\{ {{0^p}{1^q}{0^r}\left| ...

GATE CSE 2012

Consider the set of strings on $$\left\{ {0,1} \right\}$$ in which, every substring of $$3$$ symbols has at most two zeros. For example, $$001110$$ an...

GATE CSE 2011

Definition of the language $$L$$ with alphabet $$\left\{ a \right\}$$ is given as following. $$L = \left\{ {{a^{nk}}} \right.\left| {k > 0,\,n} \ri...

GATE CSE 2010

Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1's} \right\},$$ i.e $$L$$ is th...

GATE CSE 2010

Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $$w.$$ What is the minimum numb...

GATE CSE 2009

$$L = {L_1} \cap {L_2}$$ where $${L_1}$$ and $${L_2}$$ are languages defined as follows.
$${L_1} = \left\{ {{a^m}{b^m}\,c\,{a^n}{b^n}\left| {m,n \ge...

GATE CSE 2009

The above $$DFA$$ accepts the set of all strings over $$\left\{ {0,\,\,1} \right\}$$ that...

GATE CSE 2008

Given below are two finite state automata ($$ \to $$ indicates the start state and $$F$$ indicates a final state)
Which of the following represen...

GATE CSE 2008

Match the following $$NFAs$$ with the regular expressions they correspond to
...

GATE CSE 2008

Which of the following are regular sets?
...

GATE CSE 2007

A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\left\{ {0,1} \right\}}^ * },\,\,}...

GATE CSE 2007

Which of the following languages is regular?

GATE CSE 2007

Consider the following finite state automation
The language accepted by this automation is given by the regular expression...

GATE CSE 2007

Consider the following finite state automation
The minimum state automation equivalent to the above $$FSA$$ has the following number of states...

GATE CSE 2006

If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$$ s in $$s$$ and $${n_1}\left(...

GATE CSE 2006

Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ accepting this language is

GATE CSE 2005

Consider the machine $$M:$$ The language recognized by $$M$$ is:
...

GATE CSE 2004

The following finite state machine accepts all those binary strings in which the number of $$1's$$ and $$0's$$ are respectively
...

GATE CSE 2003

Consider the $$NFA$$ $$M$$ shown below.
Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language accepted by the $$NFA$$, $${M_1}$...

GATE CSE 2003

Consider the following deterministic finite state automation $$M.$$
Let $$S$$ denote the set of seven bit binary strings in which the first, the fo...

GATE CSE 2002

The smallest finite automaton which accepts the language
$$L = \left. {\left\{ x \right.} \right|$$ length of $$x$$ is divisible by $$\left. 3 \righ...

GATE CSE 2002

The Finite state machine described by the following state diagram with $$A$$ as starting state, where an arc label is $$x/y$$ and $$x$$ stands for $$1...

GATE CSE 2001

Consider a $$DFA$$ over $$\sum { = \left\{ {a,\,\,b} \right\}} $$ accepting all strings which have number of $$a'$$s divisible by $$6$$ and number of ...

GATE CSE 2001

Consider the following languages:
$${L_1} = \left\{ {w\,w\left| {w \in {{\left\{ {a,\,b} \right\}}^ * }} \right.} \right\}$$
$${L_2} = \left\{ {w\,{w^...

GATE CSE 2000

What can be said about a regular language $$L$$ over $$\left\{ a \right\}$$ whose minimal finite state automation has two states?

GATE CSE 1998

Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum state deterministic finite-state a...

GATE CSE 1997

Which one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not containing $$100$$ as substring?

GATE CSE 1995

A finite state machine with the following state table has a single input $$X$$ and a single out $$Z$$.
If the initial state is unknown, then the sh...

GATE CSE 1995

Which of the following definitions below generates the same language as $$L$$
Where $$L = {\left\{ x \right.^n}{y^n}\left| {n \ge \left. 1 \right\}} ...

GATE CSE 1994

The number of sub-strings (of all lengths inclusive) that can be formed from a character string of length $$n$$ is

GATE CSE 1994

The regular expression for the language recognized by the finite state automation of is _________.
...

GATE CSE 1992

Which of the following regular expression identities are true?

GATE CSE 1992

If $$G$$ is a context-free grammar and $$w$$ is a string of length $$n$$ in $$L(G),$$ how long is a derivation of $$w$$ in $$G,$$ if $$G$$ is Chomsky ...

GATE CSE 1991

Let $$r = 1\,{\left( {1 + 0} \right)^ * },s = {11^ * }\,0$$ and $$\,t = {1^ * }\,0$$ be three regular expressions. Which one of the following is true?

GATE CSE 1990

Let $${R_1}$$ and $${R_2}$$ be regular sets defined over the alphabet $$\sum \, $$ then:

GATE CSE 1989

How many substrings (of all lengths inclusive ) can be formed from a character string of length $$n$$? Assume all characters to be distinct. Prove you...

## Marks 5

GATE CSE 1994

Given that language $${L_1}$$ is regular and that the language $${L_1} \cap {L_2}$$ is regular is the language $${L_2}$$ is always regular?

GATE CSE 1989

Is the class of regular sets closed under infinite union? Explain.

GATE CSE 1987

Give the regular expression over $${\left\{ {0,\,\,1} \right\}}$$ to denote the set of proper non-null substrings of the string $$0110$$.

GATE CSE 1987

Give minimal $$DFA$$ that performs as a Mod-$$3$$ $$1's$$ counter, i.e., outputs a $$1$$ each time the number of $$1's$$ in the input sequence is a se...