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 activity by air1ankit
User air1ankit
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User air1ankit
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
4
answers
1
GATE20197
answered
4 days
ago
in
Theory of Computation

1.7k
views
gate2019
theoryofcomputation
regularlanguages
4
answers
2
GATE2019GA1
The expenditure on the project _____ as follows: equipment Rs.$20$ lakhs, salaries Rs.$12$ lakhs, and contingency Rs.$3$ lakhs. break down break breaks down breaks
answered
Feb 12
in
Verbal Ability

2.8k
views
gate2019
generalaptitude
verbalability
5
answers
3
GATE19943.9
Every subset of a countable set is countable. State whether the above statement is true or false with reason.
answer edited
Jan 27
in
Set Theory & Algebra

500
views
gate1994
settheory&algebra
normal
sets
descriptive
5
answers
4
GATE199526
Consider the relation scheme $R(A, B, C)$ with the following functional dependencies: $A, B → C,$ $C → A$ Show that the scheme R is in $3NF$ but not in $\text{BCNF}$. Determine the minimal keys of relation $R$.
answered
Jan 8
in
Databases

1.4k
views
gate1995
databases
databasenormalization
normal
1
answer
5
GATE200630
For $s\in (0+1)^{*}$ let $d(s)$ denote the decimal value of $s$ (e.g. $d (101) = 5$ ). Let $L=\left \{ s\in (0+1)^*\mid d(s) \text{ mod } 5=2 \text{ and }d(s) \text{ mod } 7\neq 4 \right \}$ Which one of the following statements is true? $L$ is recursively enumerable, but not recursive $L$ is recursive, but not contextfree $L$ is contextfree, but not regular $L$ is regular
commented
Dec 22, 2018
in
Theory of Computation

1.6k
views
gate2006
theoryofcomputation
normal
identifyclasslanguage
4
answers
6
GATE2005IT4
Let $L$ be a regular language and $M$ be a contextfree language, both over the alphabet $Σ$. Let $L^c$ and $M^c$ denote the complements of $L$ and $M$ respectively. Which of the following statements about the language $L^c\cup M^c$ is TRUE? It is necessarily regular but not necessarily contextfree. It is necessarily contextfree. It is necessarily nonregular. None of the above
commented
Dec 22, 2018
in
Theory of Computation

1.8k
views
gate2005it
theoryofcomputation
normal
identifyclasslanguage
3
answers
7
GATE19903viii
Choose the correct alternatives (More than one may be correct). Let $R_{1}$ and $R_{2}$ be regular sets defined over the alphabet $\Sigma$ Then: $R_{1} \cap R_{2}$ is not regular. $R_{1} \cup R_{2}$ is regular. $\Sigma^{*}R_{1}$ is regular. $R_{1}^{*}$ is not regular.
commented
Dec 20, 2018
in
Theory of Computation

1.4k
views
gate1990
normal
theoryofcomputation
regularlanguages
0
answers
8
MadeEasy
A)20,60 B)20,10 C)10,60 D)Garbage Value
comment edited
Dec 17, 2018
in
Programming

46
views
madeeasytestseries
madeeasybooklet
6
answers
9
GATE200941
The above DFA accepts the set of all strings over $\{0,1\}$ that begin either with $0$ or $1$. end with $0$. end with $00$. contain the substring $00$.
commented
Dec 14, 2018
in
Theory of Computation

2.5k
views
gate2009
theoryofcomputation
finiteautomata
easy
5
answers
10
GATE200849
Given below are two finite state automata ( $\rightarrow$ indicates the start state and $F$ indicates a final state) Y $a$ $b$ $\rightarrow$ $1$ $1$ $2$ $2 (F)$ $2$ $1$ Z $a$ $b$ $\rightarrow$ $1$ $2$ $2$ $2 (F)$ $1$ $1$ Which of the following represents the product automaton $Z \times Y$? $a$ ... $P$ $S$ $Q$ $P$ $a$ $b$ $\rightarrow$ $P$ $S$ $Q$ $Q$ $S$ $R$ $R(F)$ $Q$ $P$ $S$ $Q$ $P$
commented
Dec 14, 2018
in
Theory of Computation

3.8k
views
gate2008
normal
theoryofcomputation
finiteautomata
3
answers
11
GATE2007IT71
Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which of the following nondeterministic finite automata recognizes the language defined by the regular expression $R$? Edges labeled $\lambda $ denote transitions on the empty string.
commented
Dec 14, 2018
in
Theory of Computation

2k
views
gate2007it
theoryofcomputation
finiteautomata
normal
1
answer
12
GATE200729
A minimum state deterministic finite automaton accepting the language $L=\{w\mid w \in \{0, 1\}^*,$ number of $0$s and $1$s in $w$ are divisible by $3$ and $5$, respectively $\}$ has $15$ states $11$ states $10$ states $9$ states
commented
Dec 14, 2018
in
Theory of Computation

1.5k
views
gate2007
theoryofcomputation
finiteautomata
normal
4
answers
13
GATE2005IT37
Consider the nondeterministic finite automaton (NFA) shown in the figure. State $X$ is the starting state of the automaton. Let the language accepted by the NFA with $Y$ as the only accepting state be $L1$. Similarly, let the language accepted by the NFA with $Z$ as the ... following statements about $L1$ and $L2$ is TRUE? $L1 = L2$ $L1 \subset L2$ $L2 \subset L1$ None of the above
commented
Dec 12, 2018
in
Theory of Computation

2.8k
views
gate2005it
theoryofcomputation
finiteautomata
normal
3
answers
14
GATE2004IT41
Let $M=(K, Σ, \sigma, s, F)$ be a finite state automaton, where $K = \{A, B\}, Σ = \{a, b\}, s = A, F = \{B\},$ $\sigma(A, a) = A, \sigma(A, b) = B, \sigma(B, a) = B \text{ and} \ \sigma(B, b) = A$ A grammar to generate the language accepted by $M$ can be specified ... $\{A → bB, A → aB, B → aA, B → bA, B → \epsilon)$ $\{A → aA, A → bA, B → aB, B → bA, A → \epsilon)$
commented
Dec 12, 2018
in
Theory of Computation

1.2k
views
gate2004it
theoryofcomputation
finiteautomata
normal
3
answers
15
GATE200486
The following finite state machine accepts all those binary strings in which the number of $1$’s and $0$’s are respectively: divisible by $3$ and $2$ odd and even even and odd divisible by $2$ and $3$
commented
Dec 12, 2018
in
Theory of Computation

1.3k
views
gate2004
theoryofcomputation
finiteautomata
easy
1
answer
16
What will be the R.E of this DFA
I'm getting (a+ba*b)*a*b
commented
Dec 12, 2018
in
Theory of Computation

172
views
finiteautomata
regs
regularexpressions
1
answer
17
GATE200221
We require a four state automaton to recognize the regular expression $(a\mid b)^*abb$ Give an NFA for this purpose Give a DFA for this purpose
commented
Dec 12, 2018
in
Theory of Computation

702
views
gate2002
theoryofcomputation
finiteautomata
normal
descriptive
1
answer
18
TIFR 2019
What would be the number of distinct minimum cost spanning trees? A.32 B.64 C.16 D.8
commented
Dec 12, 2018
in
Algorithms

433
views
tifr2019
algorithms
graphalgorithms
0
answers
19
Decidability
Match the following 1.P 2.NP 3.NPComplete 4. NPHard 1.Decidable 2.Undecidable
commented
Dec 12, 2018
in
Theory of Computation

56
views
theoryofcomputation
1
answer
20
GATE 2016 Matrices
commented
Dec 12, 2018
in
Linear Algebra

34
views
0
answers
21
made_easy_test_2019 (Algorithms)
explain how to solve the above question !
commented
Dec 11, 2018
in
Algorithms

79
views
algorithms
sorting
0
answers
22
Madeeasytestseries
Do we count the return type of main as 1 token? Answer given is 29 if we don't count it.
commented
Dec 11, 2018
in
Compiler Design

55
views
1
answer
23
Online and Offline Sorting Algorithms
How to know that whether a sorting algorithm is online or offline ? For example , Insertion sort is online but Merge Sort is offline..Please explain ..
commented
Dec 11, 2018
in
Algorithms

174
views
algorithms
sorting
3
answers
24
GATE2004IT26
A subnet has been assigned a subnet mask of $255.255.255.192$. What is the maximum number of hosts that can belong to this subnet? $14$ $30$ $62$ $126$
commented
Dec 11, 2018
in
Computer Networks

1.5k
views
gate2004it
computernetworks
subnetting
normal
4
answers
25
GATE200651, ISRO201634
Consider the following recurrence: $ T(n)=2T\left ( \sqrt{n}\right )+1,$ $T(1)=1$ Which one of the following is true? $ T(n)=\Theta (\log\log n)$ $ T(n)=\Theta (\log n)$ $ T(n)=\Theta (\sqrt{n})$ $ T(n)=\Theta (n)$
commented
Dec 9, 2018
in
Algorithms

8.2k
views
algorithms
recurrence
isro2016
gate2006
3
answers
26
GATE 2015 Aptitude Set 4 Q5
Five teams have to compete in a league, with every team playing every other team exactly once, before going to the next round. How many matches will have to be held to complete the league round of matches? (A) 20 (B) 10 (C) 8 (D) 5
commented
Nov 30, 2018
in
Numerical Ability

1k
views
gate2015aptiset4
numericalability
permutationsandcombinations
1
answer
27
Ace TestSeries
What is the time complexity of T(n) = T(n/3) + T(n/9) +n?
commented
Nov 30, 2018
in
Algorithms

87
views
algorithms
testseries
timecomplexity
acetestseries
2
answers
28
GATE20143GA4
Which number does not belong in the series below? $2, 5, 10, 17, 26, 37, 50, 64$ $17$ $37$ $64$ $26$
answered
Nov 30, 2018
in
Numerical Ability

811
views
gate20143
numericalability
numberseries
easy
5
answers
29
GATE201358
What will be the maximum sum of $44, 42, 40, \dots$ ? $502$ $504$ $506$ $500$
answered
Nov 30, 2018
in
Numerical Ability

1.4k
views
gate2013
numericalability
easy
numberseries
1
answer
30
GATE200647
Consider the following graph: Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm? $(ab),(df),(bf),(dc),(de)$ $(ab),(df),(dc),(bf),(de)$ $(df),(ab),(dc),(bf),(de)$ $(df),(ab),(bf),(de),(dc)$
commented
Nov 27, 2018
in
Algorithms

1.3k
views
gate2006
algorithms
graphalgorithms
spanningtree
normal
4
answers
31
GATE19941.23
Consider the following two functions: $g_1(n) = \begin{cases} n^3 \text{ for } 0 \leq n \leq 10,000 \\ n^2 \text{ for } n \geq 10,000 \end{cases}$ $g_2(n) = \begin{cases} n \text{ for } 0 \leq n \leq 100 \\ n^3 \text{ for } n > 100 \end{cases}$ Which of the following is true? ... $g_1(n) \text{ is } O(n^3)$ $g_2(n) \text{ is } O(g_1(n))$ $g_2(n) \text{ is } O(n)$
commented
Nov 25, 2018
in
Algorithms

2.2k
views
gate1994
algorithms
asymptoticnotations
normal
2
answers
32
GATE20022.2
Consider the following multiplexer where $I0, I1, I2, I3$ are four data input lines selected by two address line combinations $A1A0=00,01,10,11$ respectively and $f$ is the output of the multiplexor. EN is the Enable input. The function $f(x,y,z)$ implemented by the above circuit is $xyz'$ $xy + z$ $x + y$ None of the above
commented
Nov 22, 2018
in
Digital Logic

2.8k
views
gate2002
digitallogic
circuitoutput
normal
2
answers
33
GATE2016218
Consider the following types of languages: $L_{1}$: Regular, $L_{2}$: Contextfree, $L_{3}$: Recursive, $L_{4}$: Recursively enumerable. Which of the following is/are TRUE ? $\bar{L_{3}} \cup L_{4}$ is recursively enumerable. $\bar{L_{2}} \cup L_{3}$ ... contextfree. $L_{1} \cup \bar{L_{2}}$ is contextfree. I only. I and III only. I and IV only. I, II and III only.
commented
Nov 20, 2018
in
Theory of Computation

2.7k
views
gate20162
theoryofcomputation
regularlanguages
contextfreelanguage
closureproperty
normal
1
answer
34
GATE200377
A uniprocessor computer system only has two processes, both of which alternate $10$ $\text{ms}$ CPU bursts with $90$ $\text{ms}$ I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed ... scheduling Static priority scheduling with different priorities for the two processes Round robin scheduling with a time quantum of $5$ $\text{ms}$
commented
Nov 19, 2018
in
Operating System

4.4k
views
gate2003
operatingsystem
processschedule
normal
4
answers
35
ISRO200711, GATE20011.19
Consider a set of n tasks with known runtimes $r_1, r_2, \dots r_n$ to be run on a uniprocessor machine. Which of the following processor scheduling algorithms will result in the maximum throughput? Round Robin Shortest job first Highest response ratio next first come first served
commented
Nov 19, 2018
in
Operating System

3.9k
views
isro2007
operatingsystem
processschedule
gate2001
6
answers
36
GATE2013ce10
Abhishek is elder to Savar. Savar is younger to Anshul. Which of the given conclusions is logically valid and is inferred from the above statements? Abhishek is elder to Anshul Anshul is elder to Abhishek Abhishek and Anshul are of the same age No conclusion follows
answered
Nov 19, 2018
in
Numerical Ability

489
views
gate2013ce
logicalreasoning
agerelation
1
answer
37
DBMS #DOUBT ...
correct???
answer selected
Nov 17, 2018
in
Databases

50
views
databases
functionaldependencies
2
answers
38
GATE199202,xix
02. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: (xix) Contextfree languages are: closed under union closed under complementation closed under intersection closed under Kleene closure
commented
Oct 27, 2018
in
Theory of Computation

691
views
gate1992
contextfreelanguage
theoryofcomputation
normal
3
answers
39
GATE19872k
State whether the following statements are TRUE or FALSE: The intersection of two CFL's is also a CFL.
commented
Oct 27, 2018
in
Theory of Computation

412
views
gate1987
theoryofcomputation
contextfreelanguage
3
answers
40
GATE2016118
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive $0$'s and two consecutive $1$'s? $(0+1 )^ *0011 (0+1)^* +(0+1)^*1100(0+1)^*$ $(0+1)^* (00(0+1)^*11+11(0+1)^*00)(0+1)^*$ $(0+1)^*00(0+1)^* + (0+1)^*11 (0+1)^*$ $00(0+1)^*11 +11(0+1)^*00$
comment edited
Oct 23, 2018
in
Theory of Computation

4.2k
views
gate20161
theoryofcomputation
regularexpressions
normal
47,913
questions
52,293
answers
182,250
comments
67,738
users