GATE CSE
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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.
Recent activity by Praveen Saini
User Praveen Saini
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User Praveen Saini
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
4
answers
1
GATE2017225
The minimum possible number of states of a deterministic finite automaton that accepts the regular language $L$ = {$w_{1}aw_{2}$  $w_{1},w_{2}$ $\in$ $\left \{ a,b \right \}^{*}$ , $\left  w_{1} \right  = 2, \left  w_{2} \right \geq 3$} is ______________ .
answer reshown
Feb 19
in
Theory of Computation

940
views
theoryofcomputation
gate20172
dfa
numericalanswers
2
answers
2
GATE2017227
If $w, x, y, z$ are Boolean variables, then which one of the following is INCORRECT? $wz+w(x+y)+x(x_y) = x+wy$ $\overline{w \bar{x}(y+\bar{z})} + \bar{w}x = \bar{w} + x + \bar{y}z$ $(w \bar{x}(y+x\bar{z}) + \bar{w} \bar{x}) y = x \bar{y}$ $(w+y)(wxy+wyz) = wxy+wyz$
answer selected
Feb 14
in
Digital Logic

756
views
gate20172
digitallogic
booleanexpressions
normal
2
answers
3
GATE2017128
The value of $\lim_{x\rightarrow 1} \frac{x^{7}2x^{5}+1}{x^{3}3x^{2}+2}$ (A) is 0 (B) is 1 (C) is 1 (D) does not exist
answer selected
Feb 14
in
Calculus

470
views
gate20171
calculus
limits
normal
3
answers
4
GATE2017232
Consider the following expression grammar G: E > ET $\mid$ T T > T + F $\mid$ F F > (E) $\mid$ id Which of the following grammars is not left recursive, but is equivalent to G? E > ET $\mid$ T T > T +F $\mid$ F F > (E) $ ... (E) $\mid$ id E > TX X > TX $\mid$ $\epsilon$ T > +FY $\mid$ $\epsilon$ F > (E) $\mid$ id
answer selected
Feb 14
in
Compiler Design

570
views
gate20172
2
answers
5
GATE20171GA4
Find the smallest number $y$ such that $y$ x 162 is a perfect cube. (A) 24 (B) 27 (C) 32 (D) 36
answer selected
Feb 14
in
Numerical Ability

434
views
gate20171
2
answers
6
GATE2007IT46
The two grammars given below generate a language over the alphabet {x, y, z} G1 : S → x  z  x S  z S  y B B → y  z  y B  z B G2 : S → y  z  y S  z S  x B B → y  y S Which one of the following choices ... No y appears after any x G2 : Every x is followed by at least one y G1 : No y appears after any x G2 : Every y is followed by at least one x
commented
Dec 31, 2016
in
Theory of Computation

252
views
gate2007it
theoryofcomputation
normal
1
answer
7
GATE 2008 IISC Baanglr Paper
Three values of x and y are to be fitted in a stright line in the form of y=a+bx by the method of least squares Given SIGMA x =6 SIGMA y=21 SIGMA x*x = 14 SIGMA xy = 46 Find the values of a and b
commented
Dec 31, 2016
in
Probability

159
views
1
answer
8
GATE1998_4
Design a deterministic finite state automaton (using minimum number of states) that recognizes the following language: $L=\{w \in \{0, 1\}^* \mid w$ interpreted as binary number (ignoring the leading zeros) is divisible by five $\}.$
commented
Dec 24, 2016
in
Theory of Computation

450
views
gate1998
theoryofcomputation
minimalstateautomata
normal
1
answer
9
GATE200779
Consider the CFG with $\left\{S, A, B\right\}$ as the nonterminal alphabet, $\{a, b\}$ as the terminal alphabet, S as the start symbol and the following set of production rules: S $\rightarrow$aB S$\rightarrow$bA B $\rightarrow$ b ... rightarrow$ aS B $\rightarrow$ aBB S $\rightarrow$ bAA For the string $aabbab$, how many derivation trees are there? 1 2 3 4
commented
Dec 17, 2016
in
Compiler Design

210
views
gate2007
compilerdesign
grammar
normal
2
answers
10
GATE2006IT31
Which of the following languages is accepted by a nondeterministic pushdown automaton (PDA) but NOT by a deterministic PDA? $\{a^nb^nc^n \mid n ≥ 0\}$ $\{a^lb^mc^n \mid l ≠ m \text{ or } m ≠ n\}$ $\{a^nb^n \mid n ≥ 0\}$ $\{a^mb^n \mid m, n ≥ 0\}$
commented
Dec 17, 2016
in
Theory of Computation

436
views
gate2006it
theoryofcomputation
pda
normal
3
answers
11
GATE20152_35
Consider the alphabet $\Sigma = \{0, 1\}$, the null/empty string $\lambda$ and the set of strings $X_0, X_1, \text{ and } X_2$ generated by the corresponding nonterminals of a regular grammar. $X_0, X_1, \text{ and } X_2$ are related as follows. $X_0 = 1 X_1$ $X_1 = 0 ... strings in $X_0$? 10(0*+(10)*)1 10(0*+(10)*)*1 1(0+10)*1 10(0+10)*1 +110(0+10)*1
commented
Dec 9, 2016
in
Theory of Computation

1.2k
views
gate20152
theoryofcomputation
regularexpressions
grammar
normal
1
answer
12
The regular expression corresponding to the finite automata given below is
answered
Dec 2, 2016
in
Theory of Computation

93
views
2
answers
13
GATE2014115
Which one of the following is TRUE? The language $L = \left\{a^nb^n \mid n \geq 0\right\}$ is regular. The language $L = \left\{a^n \mid n \text{ is prime }\right\}$ is regular. The language $L$= $\left\{ w \mid w \text{ has } 3k+1 \ ... regular. The language $L = \left\{ww \mid w \in \Sigma^* \text{ with } \Sigma = \left\{0,1\right\}\right\}$ is regular.
commented
Nov 19, 2016
in
Theory of Computation

455
views
gate20141
theoryofcomputation
regularset
normal
4
answers
14
GATE1992_04_c
Design a 3bit counter using Dflip flops such that not more than one flipflop changes state between any two consecutive states.
commented
Nov 19, 2016
in
Digital Logic

302
views
gate1994
digitallogic
flipflop
1
answer
15
GATE201040
Consider the languages $L1=\{0^i1^j\ \mid i \neq j\}, $ $L2=\{0^i1^j\mid i=j\},$ $L3=\{0^i1^j \mid i=2j+1\},$ $L4=\{0^i1^j \mid i\neq2j\}$ Only $L2$ is context free. Only $L2$ and $L3$ are context free. Only $L1$ and $L2$ are context free. All are context free
commented
Nov 19, 2016
in
Theory of Computation

556
views
gate2010
theoryofcomputation
contextfree
identifyclasslanguage
normal
1
answer
16
GATE200221
We require a four state automaton to recognize the regular expression (a/b)*abb Give an NFA for this purpose Give a DFA for this purpose
commented
Nov 17, 2016
in
Theory of Computation

216
views
gate2002
theoryofcomputation
minimalstateautomata
normal
descriptive
2
answers
17
GATE198712a
The Boolean expression $A \oplus B \oplus A$ is equivalent to $AB + \bar {A}\bar B$ $\bar{A}B+A\bar{B}$ $B$ $\bar{A}$
answer selected
Nov 15, 2016
in
Digital Logic

101
views
gate1987
digitallogic
booleanexpressions
1
answer
18
virtual gate 2
Let $L_1$ and $L_2$ be two arbitrary languages, choose incorrect statement(s) $\text{if}\; L_1.L_2\;\text{ is regular then }L_2.L_1\;\text{ is also regular.}$ $L_1 = L_2 \;\text{iff}\; L_1 \backslash L_2 = \phi \; \text{and}\; L_2 \backslash ... Sigma^* \backslash L \;\text{is regular}$ (\ denotes set difference) Only (i) (i) and (ii) (ii) and (iii) All
commented
Oct 27, 2016
in
Theory of Computation

232
views
virtualgate
theoryofcomputation
identifyclasslanguage
2
answers
19
GATE20007
Construct as minimal finite state machine that accepts the language, over {0,1}, of all strings that contain neither the sub string 00 nor the sub string 11. Consider the grammar S → aSAb S → ∊ A → bA A → ∊ where S, A are nonterminal symbols with ... aibj for some i, j ≥ 0, where i and j satisfy some condition. What is the condition on the values of i and j?
answer selected
Oct 26, 2016
in
Theory of Computation

271
views
gate2000
theoryofcomputation
descriptive
3
answers
20
DFA: No of states
How many states in the minimal dfa which accepts all string of language L={ w  w € (a+b)* } whose string length divide by 2 or 4 ?
answer selected
Oct 13, 2016
in
Theory of Computation

91
views
minimalstateautomata
1
answer
21
#minimizeddfa
Minimized DFA for a*b* + b*a* and a+b+ + b+a+
answer selected
Oct 13, 2016
in
Theory of Computation

92
views
#regularlanguage
#dfa
3
answers
22
NFA for the language, L= (ab, ba)* would have how many states?
commented
Oct 11, 2016
in
Theory of Computation

287
views
theoryofcomputation
finiteautomata
1
answer
23
Regular/ Non Regular. Language is regular or not?
commented
Oct 11, 2016
in
Theory of Computation

231
views
theoryofcomputation
identifyclasslanguage
2
answers
24
ToC \ Reg Expression
Give a regular expression for L = {set of all strings in which number of a's are multiples of 3} ∑={a,b,c}
comment reshown
Oct 10, 2016

115
views
theoryofcomputation
regularexpressions
3
answers
25
Minimal FA
What is the number of states in a minimal FA which accepts all strings over (0,1)* where every string starts with 100 and the length of the string is congruent to 1(mod4) I am getting 11 states. Ans given is 8. While doing the cross product , is it ensured that , I will get the minimal DFA ? or do I have to minimise after the cross product ?
answer selected
Oct 8, 2016
in
Theory of Computation

101
views
theoryofcomputation
compoundautomata
1
answer
26
#virtual gate
option A) 00 B) 10 C) 11 D) state 11 is not recahable
answer selected
Oct 8, 2016
in
Digital Logic

70
views
digitallogic
1
answer
27
GATE1998_1.10
Which of the following set can be recognized by a Deterministic Finite state Automaton? The numbers $1, 2, 4, 8, \dots 2^n, \dots$ written in binary The numbers $1, 2, 4, 8,\dots 2^n, \dots$ written in unary The set of binary string in which the number of zeros is the same as the number of ones. The set $\{1, 101, 11011, 1110111, \dots\}$
commented
Oct 3, 2016
in
Theory of Computation

433
views
gate1998
theoryofcomputation
finiteautomata
normal
2
answers
28
GATE20161GA10
In a process, the number of cycles to failure decreases exponentially with an increase in load. At a load of $80$ units, it takes $100$ cycles for failure. When the load is halved, it takes $10000 \ \text{cycles}$ for failure.The load for which the failure will happen in $5000 \ \text{cycles}$ is _____________. $40.00$ $46.02$ $60.01$ $92.02$
commented
Oct 3, 2016
in
Numerical Ability

2.9k
views
gate20161
numericalability
proportions
normal
1
answer
29
UGCNETAUG2016II10
Match the following : LISTI LISTII a. Controlled Inverter i. a circuit that can add 3 bits b. Full adder ii. a circuit that can add two binary numbers c. Half adder iii. a circuit that transmits a binary word or its 1’s complement d. Binary adder iv. a logic circuit that adds 2 bits Codes : a b c d iii ii iv i ii iv i iii iii iv i ii iii i iv ii
answer selected
Sep 24, 2016
in
Others

92
views
ugcnetaug2016ii
1
answer
30
Number of multiplexer required
The number of two input multiplexers required to construct a $2^{10}$ input multiplexer is, A. $31$ B. $10$ C. $127$ D. $1023$
commented
Sep 24, 2016
in
Digital Logic

102
views
digitallogic
testseries
multiplexer
1
answer
31
How can i find the expression value
commented
Sep 21, 2016
in
Digital Logic

85
views
1
answer
32
Dexter C: Find Regular sets
Two of the Following three sets are always regular for any regular set A. Which are they? Give two proofs and one counter example? (a) { x  xx ∈ A } (b) { x  Ǝy y = 22^x and xy ∈ A } (c) { x  Ǝy y = logx and xy∈ A}
commented
Sep 19, 2016
in
Theory of Computation

136
views
theoryofcomputation
regularlanguage
finiteautomata
dexter
0
answers
33
VirtualGate 2015 TOC: Regular language FirstThirds
commented
Sep 19, 2016
in
Theory of Computation

124
views
regularlanguage
theoryofcomputation
virtualgate
regularset
2
answers
34
VirtualGate 2015 TOC: Which Language is reguar
commented
Sep 19, 2016
in
Theory of Computation

192
views
virtualgate
theoryofcomputation
regularlanguage
regularset
2
answers
35
Digital logic
A number N is stored in a 4bit 2's complement form as A3 A2 A1 A0 It is copied into a 6bit register and after a few operations,the final bit pattern is A3 A3 A2 A1 A0 A1 The value of this bit pattern in 2's complement form is given in terms of original number N as A) 32A3 +2N +1 B) 32A3 2N 1 C) 2N 1 D) 2N +1
commented
Sep 14, 2016
in
Digital Logic

94
views
digitallogic
1
answer
36
DFA sub :TOC
construct a dfa :all string with atleast one a and exactly two b's ,
answer selected
Sep 9, 2016
in
Theory of Computation

98
views
1
answer
37
push down automata
The pushdown automation $M=(\{q_0, q_1, q_2\}, \{a,b\}, \{0,1\}, \delta, q_0, 0, \{q_0\})$ with $\delta(q_0,a,0)=\{q_1,10)\}$ $\delta(q_1,a,1)=\{q_1,11)\}$ $\delta(q_0,b,1)=\{q_2,\lambda)\}$ $\delta(q_2,b,1)=\{q_2,\lambda)\}$ $\delta(q_2,\lambda,0)= ... \geq 0\}$ $L=\{a^nb^n \mid n \geq 0\}$ $L=\{a^nb^m \mid n,m > 0\}$ $L=\{a^nb^n \mid n > 0\}$
commented
Sep 9, 2016
in
Theory of Computation

106
views
theoryofcomputation
pushdownautomata
1
answer
38
Convert Binary to excess3
Someone help me out.
commented
Sep 9, 2016
in
Digital Logic

272
views
digitallogic
1
answer
39
language identify
consider all palindrome even if they are sentencein English which are of finite lengh. let this language be L a.L is regular set b.L is finite set c. L is dcfl d.L is CFL
answer selected
Sep 8, 2016
in
Theory of Computation

44
views
1
answer
40
UGCNETDec2010II7
$AB + (\bar{A+B})$ is equivalent to $A \bigoplus B$ $A \bigodot B$ $(A \bigoplus B) \bigodot A$ $(A \bigodot B) \bigoplus A$
answer selected
Sep 5, 2016
in
Others

49
views
ugcnetdec2010ii
21,440
questions
26,754
answers
60,924
comments
22,934
users