The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged gb2019toc1
+2
votes
1
answer
1
GATEBOOK2019TOC11
Consider the DFA shown below: The number of states in the equivalent minimized DFA is ______
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

202
views
gb2019toc1
numericalanswers
minimalstateautomata
+4
votes
2
answers
2
GATEBOOK2019TOC12
What is the minimum number of states in the DFA for the following language $(\Sigma = \{ a,b \}) ? $________ $L= \{w \mid w \in \Sigma^* \text{ w has exactly two a's and at least two b's} \}$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

218
views
gb2019toc1
numericalanswers
+2
votes
1
answer
3
GATEBOOK2019TOC13
Let the input alphabet be $\{0,1\}$. The minimum number of states for a DFA, which accepts "All strings containing $10$ but not $101$" is ______
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

251
views
gb2019toc1
numericalanswers
0
votes
1
answer
4
GATEBOOK2019TOC14
Let $L$ contains set of all strings over $\{a,b\}$ where there are exactly $4$ occurrences of $‘bb’$ substring. Which of the following is true? $L$ is finite and regular $L$ is infinite but regular $L$ is not regular None
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

131
views
gb2019toc1
0
votes
1
answer
5
GATEBOOK2019TOC15
$M_1$ and $M_2$ are $2$ minimal DFAs containing $n_1$ and $n_2$ number of states $(n_1 \neq n_2).$ Which of the following statements is true? $M_1$ and $M_2$ can represent the same language If $n_1 > n_2,$ $L(M_1) \supset L(M_2)$ If $n_1 > n_2,$ $L(M_1) \subset L(M_2)$ None of the above
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

134
views
gb2019toc1
finiteautomata
0
votes
2
answers
6
GATEBOOK2019TOC16
Consider an NFA with $5$ states. The minimum number of states in the equivalent DFA will be ____ $5$ $1$ $16$ None of these
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

213
views
gb2019toc1
+6
votes
4
answers
7
GATEBOOK2019TOC17
If the language accepted by a DFA contains binary strings divisible by $12$ (in decimal), the minimum number of states in it will be ______
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

477
views
gb2019toc1
numericalanswers
0
votes
1
answer
8
GATEBOOK2019TOC18
Let L1 be a regular language and L2 = L1*. Then L2 is___________ Always finite language Always infinite language and regular Need not be infinite language None
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

89
views
gb2019toc1
0
votes
1
answer
9
GATEBOOK2019TOC19
Which one of the following statements is false? DFA and NFA have same powers. NFA with one final state has same powers as NFA with more than one final states. Every epsilonNFA can be converted into an equivalent NFA without epsilon transitions DFA with single final state has the same powers as DFA with more than one final state.
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

131
views
gb2019toc1
+1
vote
1
answer
10
GATEBOOK2019TOC110
If $L$ is a regular language, which of the following is true? $L' = \{x_1x_3x_5 \ldots \mid x_0x_1x_2x_3x_4 \ldots \in L\}$ is non  regular $L'' = \{x_0x_2x_4 \ldots \mid x_0x_1x_2x_3x_4 \ldots \in L\}$ is non  regular Both $L'$ and $L''$ are nonregular Both $L'$ and $L''$ are regular
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

132
views
gb2019toc1
regularlanguages
0
votes
0
answers
11
GATEBOOK2019TOC111
Match the following regular expression with their description: i $0^+(0+1)1^+$ 1 any string that has exactly three $1$'s ii $0^*10^*10^*10^*$ 2 any string of length $3$ or greater that is one or more $0$'s are followed by one or more $1$'s iii $0^*(100^*)^*1^*$ 3 any string ... subsrting $110$ $i2, ii1, iii3, iv4$ $i2, ii1, iii4, iv3$ $i1, ii2, iii4, iv3$ $None$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

50
views
gb2019toc1
0
votes
2
answers
12
GATEBOOK2019TOC112
Each of the following is a regular expression that denotes a subset of the language recognized by the automaton above EXCEPT $0^*(11)^*0^*$ $0^*1(10^*1)^*1$ $0^*1(10^*1)^*10^*$ $0^*1(10^*1)0(100)^*$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

71
views
gb2019toc1
0
votes
1
answer
13
GATEBOOK2019TOC113
Which of the following grammar is a regular grammar and generates the same language as the regular expression $a^*+b^*+ ab?$ $S\to AB,\:A\to aA \mid \epsilon;\:B\to bB\mid \epsilon$ $S\to ab \mid A \mid B; \: A\to Aa \mid a;\: B\to Bb \mid b$ $S\to ab \mid A \mid B; \: A\to aA \mid \epsilon;\: B\to bB \mid \epsilon$ $S\to A\mid B;\: A\to aA \mid b;\: B\to Bb \mid b$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

55
views
gb2019toc1
regulargrammar
0
votes
0
answers
14
GATEBOOK2019TOC114
Consider the following finite automaton over the alphabet $\{0,1\}$. A is the starting state before so far there are no accepting states. How many numbers of states should be made accepting in order for this automaton to accept the language of strings with zero or an even number of $1$? _____
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

53
views
gb2019toc1
numericalanswers
0
votes
0
answers
15
GATEBOOK2019TOC115
Let $k \geq 2$. Let $L$ be the set of strings in $\{0,1\}^*$ such that $ x \in L$ if and only if the number of $0$'s in $x$ is divisible by $k$ and the number of $1$'s in $x$ is odd. The minimum number of states in a deterministic finite automaton (DFA) that recognizes $L$ is $k+2$ $2k$ $k \log k$ $k^2$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

97
views
gb2019toc1
0
votes
1
answer
16
GATEBOOK2019TOC116
Consider the DFA with states $\{0,1,2,3,4\},$ input alphabet set $\{0.1\},$ start state $0,$ final state $0,$ and transition function $\delta \left ( q,i \right ) = (q^2i) \mod 5 \mid i \in\{0,1\}. $The language accepted ... binary strings containing odd number of $0$'s Set of binary strings containing even number of $1$'s Set of binary strings containing odd number of $1$'s
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

81
views
gb2019toc1
finiteautomata
regularlanguages
0
votes
1
answer
17
GATEBOOK2019TOC117
Consider the following finite automaton F$_1$ that accepts a language 'L' Let F$_2$ be a finite automata which is obtained by the reversal of F$_1$. Then which of the following is correct? $L(F_1) \neq L(F_2)$ $L(F_1) = L(F_2)$ $L(F_1) \subseteq L(F_2)$ $L(F_2) \subseteq L(F_1)$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

81
views
gb2019toc1
+1
vote
1
answer
18
GATEBOOK2019TOC118
Consider the following DFA: Identify the language accepted by the DFA? All strings not containing aaa All strings not starting with aaa All strings with no more two two a’s None of these
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

73
views
gb2019toc1
0
votes
0
answers
19
GATEBOOK2019TOC119
What is the language accepted by the following NFA? $(0+1)^*0$ $(0^*1^*0^*$ $0^*1^*0^*0$ $(0+1)^*$
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

75
views
gb2019toc1
+1
vote
1
answer
20
GATEBOOK2019TOC120
Let $L_1 = a^*b^*$ and $L_2 = \{ab\}.$ $L_3 = \text{Prefix}(L_1^* \cap L_2),$ where $\text{Prefix}(L) = \{u \mid uv \in L$ for some $v\}.$ Number of strings in $L_3$ is _______
asked
Nov 12, 2018
in
Theory of Computation
by
GATEBOOK
Boss
(
13.8k
points)

128
views
gb2019toc1
regularlanguages
numericalanswers
To see more, click for the
full list of questions
or
popular tags
.
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
PSU's
Decidability Slides
AAI JE IT results out! Adv no 02/2018
Graph Theory Slides for GATECSE
Generating Function Useful Link
Follow @csegate
Gatecse
Recent questions tagged gb2019toc1
Recent Blog Comments
Thank you, lots of things got clear!
Those who have given yes. But those with 10000+...
47,080
questions
51,333
answers
177,706
comments
66,675
users