ExamSIDE
Questions
ExamSIDE.Com
Theory of Computation
Undecidability
Finite Automata and Regular Language
Push Down Automata and Context Free Language
Recursively Enumerable Language and Turing Machine
Joint Entrance Examination
JEE Main
Chemistry
Physics
Mathematics
JEE Advanced
Physics
Chemistry
Mathematics
WB JEE
Physics
Chemistry
Mathematics
Graduate Aptitude Test in Engineering
GATE CSE
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Digital Logic
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude
GATE ECE
Network Theory
Control Systems
Electronic Devices and VLSI
Analog Circuits
Digital Circuits
Microprocessors
Signals and Systems
Communications
Electromagnetics
General Aptitude
Engineering Mathematics
GATE EE
Electromagnetic Fields
Signals and Systems
Engineering Mathematics
General Aptitude
Power Electronics
Power System Analysis
Analog Electronics
Control Systems
Digital Electronics
Electrical Machines
Electric Circuits
Electrical and Electronics Measurement
GATE ME
Engineering Mechanics
Strength of Materials
Theory of Machines
Engineering Mathematics
Machine Design
Fluid Mechanics
Turbo Machinery
Heat Transfer
Thermodynamics
Production Engineering
Industrial Engineering
General Aptitude
GATE CE
Construction Material and Management
Geomatics Engineering Or Surveying
Engineering Mechanics
Hydrology
Transportation Engineering
Strength of Materials Or Solid Mechanics
Reinforced Cement Concrete
Steel Structures
Irrigation
Environmental Engineering
Engineering Mathematics
Structural Analysis
Geotechnical Engineering
Fluid Mechanics and Hydraulic Machines
General Aptitude
GATE PI
Engineering Mechanics
Strength of Materials
Theory of Machines
Engineering Mathematics
Machine Design
Fluid Mechanics
Heat Transfer
Thermodynamics
Casting
Joining of Materials
Metal Forming
Machine Tools and Machining
Metrology
Industrial Engineering
GATE IN
Engineering Mathematics
Medical
NEET
Biology
Chemistry
Physics
NEW
New Website Launch
Experience the best way to solve previous year questions with
mock tests
(very detailed analysis),
bookmark your favourite questions
,
practice
etc...
VISIT NOW
GATE CSE
Finite Automata and Regular Language
Theory of Computation
Previous Years Questions
START HERE
Marks 1
More
Which one of the following regular expressions correctly represents the language of the finite automation given below? ...
GATE CSE 2022
GO TO QUESTION
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1’s?
GATE CSE 2020
GO TO QUESTION
Consider the following statements. I. If L1 $$ \cup $$ L2 is regular, then both L1 and L2 must be regular. II. The class...
GATE CSE 2020
GO TO QUESTION
For Σ = {a, b}, let us consider the regular language L = {x | x = a2+3k or x = b10+12k, k ≥ 0}. Which one of the followi...
GATE CSE 2019
GO TO QUESTION
If L is a regular language over Σ = {a,b}, which one of the following languages is NOT regular?
GATE CSE 2019
GO TO QUESTION
Language $${L_1}$$ is defined by the grammar: $$S{}_1 \to a{S_1}b|\varepsilon $$ Language $${L_2}$$ is defined by the gr...
GATE CSE 2016 Set 2
GO TO QUESTION
The number of states in the minimum sized $$DFA$$ that accepts the language defined by the regular expression $$${\left...
GATE CSE 2016 Set 2
GO TO QUESTION
Which one of the following regular expressions represents the language: the set of all binary strings having two consecu...
GATE CSE 2016 Set 1
GO TO QUESTION
Let $$L$$ be the language represented by the regular expression $$\sum {^ * 0011\sum {^ * } } $$ where $$\sum { = \left\...
GATE CSE 2015 Set 3
GO TO QUESTION
The length of the shortest string NOT in the language (over $$\sum { = \left\{ {a,\,\,b} \right\}} $$) of the following ...
GATE CSE 2014 Set 3
GO TO QUESTION
Consider the finite automation in the following figure. What is the set of reachable states for the input string $$001...
GATE CSE 2014 Set 1
GO TO QUESTION
If $${L_1} = \left\{ {{a^n}\left| {n \ge \left. 0 \right\}} \right.} \right.$$ and $${L_2} = \left\{ {{b^n}\left| {n \ge...
GATE CSE 2014 Set 2
GO TO QUESTION
Which one of the following is TRUE?
GATE CSE 2014 Set 1
GO TO QUESTION
Consider the languages $${L_1} = \phi $$ and $${L_2} = \left\{ a \right\}.$$ Which one of the following represents $${L_...
GATE CSE 2013
GO TO QUESTION
What is the complement of the language accepted by the $$NFA$$ shown below? Assume $$\sum { = \left\{ a \right\}\,\,} $...
GATE CSE 2012
GO TO QUESTION
Let $${L_1}$$ recursive language. Let $${L_2}$$ and $${L_3}$$ be languages that are recursively enumerable but not recur...
GATE CSE 2010
GO TO QUESTION
Which one of the following languages over the alphabet $$\left\{ {0,\left. 1 \right)} \right.$$ is described by the regu...
GATE CSE 2009
GO TO QUESTION
Consider the set $$\sum {^ * } $$ of all strings over the alphabet $$\,\sum { = \,\,\,\left\{ {0,\,\,\,1} \right\}.\sum ...
GATE CSE 2003
GO TO QUESTION
The regular expression $${0^ * }\left( {{{10}^ * }} \right){}^ * $$denotes the same set as
GATE CSE 2003
GO TO QUESTION
Given an arbitrary non-deterministic finite automaton $$(NFA)$$ with $$N$$ states, the maximum number of states in an eq...
GATE CSE 2001
GO TO QUESTION
Consider the following two statements; $${S_1}\,\,:\,\,\left\{ {{0^{2n}}\left| {n \ge 1} \right.} \right\}$$ is a regula...
GATE CSE 2001
GO TO QUESTION
Let $$L$$ denote the language generated by the grammar $$S \to 0S\left. 0 \right|00.$$ Which one of the following is tru...
GATE CSE 2000
GO TO QUESTION
Let $$S$$ and $$T$$ be languages over $$\sum { = \left\{ {a,b} \right\}} $$ represented by the regular expressions $${\l...
GATE CSE 2000
GO TO QUESTION
Consider the regular expression $$(0+1)(0+1).......n$$ times. The minimum state finite automation that recognizes the la...
GATE CSE 1999
GO TO QUESTION
How many substrings of different lengths (non-zero) can be formed from a character string of length $$n$$ ?
GATE CSE 1998
GO TO QUESTION
Which of the following sets can be recognized by a Deterministic Finite-state Automation?
GATE CSE 1998
GO TO QUESTION
The string $$1101$$ does not belong to the set represented by
GATE CSE 1998
GO TO QUESTION
If the regular set $$A$$ is represented by $$A = {\left( {01 + 1} \right)^ * }$$ and the regular set $$'B'$$ is represen...
GATE CSE 1998
GO TO QUESTION
$$\sum { = \left\{ {a,b} \right\},\,\,} $$ which one of the following sets is not countable.
GATE CSE 1997
GO TO QUESTION
Let $$L \subseteq \sum {^{^ * }\,} $$ where $$\,\sum { = \,\,\left\{ {a,b} \right\}\,\,} $$ which of the following is tr...
GATE CSE 1996
GO TO QUESTION
Which two of the following four regular expressions are equivalent? (i) $${\left( {00} \right)^ * }\left( {\varepsilon ...
GATE CSE 1996
GO TO QUESTION
State True or False with one line explanation: A FSM (Finite State Machine) can be designed to add two integers of any a...
GATE CSE 1994
GO TO QUESTION
Marks 2
More
Consider the following language. L = { w ∈ {0, 1}* | w ends with the substring 011} Which one of the following de...
GATE CSE 2021 Set 1
GO TO QUESTION
Consider the following language. L = {x $$ \in $$ {a, b}* | number of a’s in x is divisible by 2 but not divisible by 3}...
GATE CSE 2020
GO TO QUESTION
Given a language $$𝐿,$$ define $${L^i}$$ as follows: $${L^0} = \left\{ \varepsilon \right\}$$ $${L^i} = {L^{i - 1}}.\...
GATE CSE 2018
GO TO QUESTION
Let $$N$$ be an $$NFA$$ with $$n$$ states. Let $$k$$ be the number of states of a minimal $$DFA$$ which is equivalent to...
GATE CSE 2018
GO TO QUESTION
Consider the following languages: $$$\eqalign{ & {L_1} = \left\{ {{a^n}{b^m}{c^{n + m}}:m,n \ge 1} \right\} \cr ...
GATE CSE 2016 Set 2
GO TO QUESTION
Consider the following two statements: $$\,\,\,\,\,\,\,{\rm I}.\,\,\,\,\,$$ If all states of an $$NFA$$ are accepting st...
GATE CSE 2016 Set 2
GO TO QUESTION
Consider the transition diagram of a $$PDA$$ given below with input alphabet $$\sum {\, = \left\{ {a,b} \right\}} $$ and...
GATE CSE 2016 Set 1
GO TO QUESTION
Consider the alphabet $$\sum { = \left\{ {0,1} \right\},} $$ the null/empty string $$\lambda $$ and the sets of strings ...
GATE CSE 2015 Set 2
GO TO QUESTION
Which of the following languages is/are regular? $${L_1}:\left\{ {wx{w^R}|w,x\, \in \left\{ {a,b} \right\}{}^ * } \right...
GATE CSE 2015 Set 2
GO TO QUESTION
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $${\left( {0 ...
GATE CSE 2015 Set 2
GO TO QUESTION
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
GO TO QUESTION
Consider the NPDA $$\left\langle {Q = \left\{ {{q_0},{q_1},{q_2}} \right\}} \right.,$$ $$\Sigma = \left \{ 0, 1 \right \...
GATE CSE 2015 Set 1
GO TO QUESTION
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences o...
GATE CSE 2014 Set 2
GO TO QUESTION
Let $${L_1} = \left\{ {w \in \left\{ {0,1} \right\}{}^ * \left| w \right.} \right.$$ has at least as many occurrences o...
GATE CSE 2014 Set 2
GO TO QUESTION
Which of the regular expression given below represent the following $$DFA?$$ ...
GATE CSE 2014 Set 1
GO TO QUESTION
Consider the following languages $${L_1} = \left\{ {{0^p}{1^q}{0^r}\left| {p,q,r \ge 0} \right.} \right\}$$ $${L_2} = \...
GATE CSE 2013
GO TO QUESTION
Consider the set of strings on $$\left\{ {0,1} \right\}$$ in which, every substring of $$3$$ symbols has at most two zer...
GATE CSE 2012
GO TO QUESTION
Definition of the language $$L$$ with alphabet $$\left\{ a \right\}$$ is given as following. $$L = \left\{ {{a^{nk}}} \r...
GATE CSE 2011
GO TO QUESTION
Let $$w$$ be any string of length $$n$$ in $${\left\{ {0,1} \right\}^ * }$$. Let $$L$$ be the set of all substrings of $...
GATE CSE 2010
GO TO QUESTION
Let $$L = \left\{ {w \in {{\left( {0 + 1} \right)}^ * }\left| {\,w} \right.} \right.$$ has even number of $$\,\left. {1'...
GATE CSE 2010
GO TO QUESTION
The above $$DFA$$ accepts the set of all strings over $$\left\{ {0,\,\,1} \right\}$$ that...
GATE CSE 2009
GO TO QUESTION
$$L = {L_1} \cap {L_2}$$ where $${L_1}$$ and $${L_2}$$ are languages defined as follows. $${L_1} = \left\{ {{a^m}{b^m}...
GATE CSE 2009
GO TO QUESTION
Match the following $$NFAs$$ with the regular expressions they correspond to ...
GATE CSE 2008
GO TO QUESTION
Which of the following are regular sets? ...
GATE CSE 2008
GO TO QUESTION
Given below are two finite state automata ($$ \to $$ indicates the start state and $$F$$ indicates a final state) W...
GATE CSE 2008
GO TO QUESTION
Consider the following finite state automation The minimum state automation equivalent to the above $$FSA$$ has the fo...
GATE CSE 2007
GO TO QUESTION
Consider the following finite state automation The language accepted by this automation is given by the regular expres...
GATE CSE 2007
GO TO QUESTION
Which of the following languages is regular?
GATE CSE 2007
GO TO QUESTION
A minimum state deterministic finite automation accepting the language $$L = \left\{ {w\left| {w \in } \right.\,\,{{\lef...
GATE CSE 2007
GO TO QUESTION
Consider the regular language $$L = {\left( {111 + 11111} \right)^ * }.$$ The minimum number of states in any $$DFA$$ ac...
GATE CSE 2006
GO TO QUESTION
If $$s$$ is a string over $${\left( {0 + 1} \right)^ * }$$ then let $${n_0}\left( s \right)$$ denote the number of $$0'$...
GATE CSE 2006
GO TO QUESTION
Consider the machine $$M:$$ The language recognized by $$M$$ is: ...
GATE CSE 2005
GO TO QUESTION
The following finite state machine accepts all those binary strings in which the number of $$1's$$ and $$0's$$ are respe...
GATE CSE 2004
GO TO QUESTION
Consider the following deterministic finite state automation $$M.$$ Let $$S$$ denote the set of seven bit binary stri...
GATE CSE 2003
GO TO QUESTION
Consider the $$NFA$$ $$M$$ shown below. Let the language accepted by $$M$$ be $$L.$$ Let $${L_1}$$ be the language acc...
GATE CSE 2003
GO TO QUESTION
The Finite state machine described by the following state diagram with $$A$$ as starting state, where an arc label is $$...
GATE CSE 2002
GO TO QUESTION
The smallest finite automaton which accepts the language $$L = \left. {\left\{ x \right.} \right|$$ length of $$x$$ is...
GATE CSE 2002
GO TO QUESTION
Consider the following languages: $${L_1} = \left\{ {w\,w\left| {w \in {{\left\{ {a,\,b} \right\}}^ * }} \right.} \right...
GATE CSE 2001
GO TO QUESTION
Consider a $$DFA$$ over $$\sum { = \left\{ {a,\,\,b} \right\}} $$ accepting all strings which have number of $$a'$$s div...
GATE CSE 2001
GO TO QUESTION
What can be said about a regular language $$L$$ over $$\left\{ a \right\}$$ whose minimal finite state automation has t...
GATE CSE 2000
GO TO QUESTION
Let $$L$$ be the set of all binary strings whose last two symbols are the same. The number of states in the minimum stat...
GATE CSE 1998
GO TO QUESTION
Which one of the following regular expressions over $$\left\{ {0,\,\,1} \right\}$$ denotes the set of all strings not co...
GATE CSE 1997
GO TO QUESTION
Which of the following definitions below generates the same language as $$L$$ Where $$L = {\left\{ x \right.^n}{y^n}\le...
GATE CSE 1995
GO TO QUESTION
A finite state machine with the following state table has a single input $$X$$ and a single out $$Z$$. If the initial...
GATE CSE 1995
GO TO QUESTION
The number of sub-strings (of all lengths inclusive) that can be formed from a character string of length $$n$$ is
GATE CSE 1994
GO TO QUESTION
The regular expression for the language recognized by the finite state automation of is _________. ...
GATE CSE 1994
GO TO QUESTION
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$$ ...
GATE CSE 1992
GO TO QUESTION
Which of the following regular expression identities are true?
GATE CSE 1992
GO TO QUESTION
Let $$r = 1\,{\left( {1 + 0} \right)^ * },s = {11^ * }\,0$$ and $$\,t = {1^ * }\,0$$ be three regular expressions. Which...
GATE CSE 1991
GO TO QUESTION
Let $${R_1}$$ and $${R_2}$$ be regular sets defined over the alphabet $$\sum \, $$ then:
GATE CSE 1990
GO TO QUESTION
How many substrings (of all lengths inclusive ) can be formed from a character string of length $$n$$? Assume all charac...
GATE CSE 1989
GO TO QUESTION
Marks 5
More
Given that language $${L_1}$$ is regular and that the language $${L_1} \cap {L_2}$$ is regular is the language $${L_2}$$...
GATE CSE 1994
GO TO QUESTION
Is the class of regular sets closed under infinite union? Explain.
GATE CSE 1989
GO TO QUESTION
Give the regular expression over $${\left\{ {0,\,\,1} \right\}}$$ to denote the set of proper non-null substrings of the...
GATE CSE 1987
GO TO QUESTION
Give minimal $$DFA$$ that performs as a Mod-$$3$$ $$1's$$ counter, i.e., outputs a $$1$$ each time the number of $$1's$$...
GATE CSE 1987
GO TO QUESTION
Joint Entrance Examination
JEE Main
JEE Advanced
WB JEE
Graduate Aptitude Test in Engineering
GATE CSE
GATE ECE
GATE EE
GATE ME
GATE CE
GATE PI
GATE IN
Medical
NEET
CBSE
Class 12