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
(
15.3k
points)

218
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
(
15.3k
points)

241
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
(
15.3k
points)

271
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
(
15.3k
points)

141
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
(
15.3k
points)

146
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
(
15.3k
points)

234
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
(
15.3k
points)

523
views
gb2019toc1
numericalanswers
+1
vote
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
(
15.3k
points)

101
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
(
15.3k
points)

163
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
(
15.3k
points)

144
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
(
15.3k
points)

58
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
(
15.3k
points)

81
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
(
15.3k
points)

61
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
(
15.3k
points)

62
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
(
15.3k
points)

111
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
(
15.3k
points)

95
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
(
15.3k
points)

95
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
(
15.3k
points)

78
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
(
15.3k
points)

84
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
(
15.3k
points)

138
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
IIT Gandhinagar review
Is DAIICT good for doing MTech ?
AIR175 : GO is enough
GATE 2019 My reasoned routine. (AIR 558)
if i can you also can
Follow @csegate
Recent questions tagged gb2019toc1
Recent Blog Comments
Brother!! your all posts are really worth to read...
Publication is not a strict requirement but you...
Thesis is necessary, but publication is not for...
According to their site
congrats man!!! u surely need guts to leave job...
48,564
questions
52,765
answers
183,387
comments
68,245
users