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
1
answer
1
Finite Automata
How to convert Regular Grammar to Deterministic Finite Automata directly?
commented
2 days
ago
in
Theory of Computation

27
views
theoryofcomputation
3
answers
2
GATE201039
Let $L=\{ w \in \:(0+1)^* \mid w\text{ has even number of }1s \}$. i.e., $L$ is the set of all the bit strings with even numbers of $1$s. Which one of the regular expressions below represents $L$? $(0^*10^*1)^*$ $0^*(10^*10^*)^*$ $0^*(10^*1)^*0^*$ $0^*1(10^*1)^*10^*$
commented
3 days
ago
in
Theory of Computation

965
views
gate2010
theoryofcomputation
regularexpressions
normal
2
answers
3
Regular expression for given FA
commented
3 days
ago
in
Theory of Computation

96
views
theoryofcomputation
regularexpressions
finiteautomata
2
answers
4
Is dead state included in Minimum DFA
commented
3 days
ago
in
Theory of Computation

54
views
theoryofcomputation
5
answers
5
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

1k
views
theoryofcomputation
gate20172
dfa
numericalanswers
4
answers
6
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

875
views
gate20172
digitallogic
booleanexpressions
normal
3
answers
7
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

546
views
gate20171
calculus
limits
normal
4
answers
8
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

742
views
gate20172
2
answers
9
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

508
views
gate20171
2
answers
10
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

264
views
gate2007it
theoryofcomputation
normal
1
answer
11
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

163
views
1
answer
12
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

468
views
gate1998
theoryofcomputation
minimalstateautomata
normal
1
answer
13
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

232
views
gate2007
compilerdesign
grammar
normal
2
answers
14
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

472
views
gate2006it
theoryofcomputation
pda
normal
3
answers
15
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.3k
views
gate20152
theoryofcomputation
regularexpressions
grammar
normal
1
answer
16
The regular expression corresponding to the finite automata given below is
answered
Dec 2, 2016
in
Theory of Computation

97
views
3
answers
17
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

482
views
gate20141
theoryofcomputation
regularset
normal
4
answers
18
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

320
views
gate1994
digitallogic
flipflop
1
answer
19
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

614
views
gate2010
theoryofcomputation
contextfree
identifyclasslanguage
normal
1
answer
20
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

223
views
gate2002
theoryofcomputation
minimalstateautomata
normal
descriptive
2
answers
21
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

125
views
gate1987
digitallogic
booleanexpressions
1
answer
22
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

236
views
virtualgate
theoryofcomputation
identifyclasslanguage
2
answers
23
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

285
views
gate2000
theoryofcomputation
descriptive
3
answers
24
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

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

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

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

239
views
theoryofcomputation
identifyclasslanguage
2
answers
28
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

118
views
theoryofcomputation
regularexpressions
3
answers
29
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

106
views
theoryofcomputation
compoundautomata
1
answer
30
#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
31
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

469
views
gate1998
theoryofcomputation
finiteautomata
normal
2
answers
32
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

3k
views
gate20161
numericalability
proportions
normal
1
answer
33
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

109
views
ugcnetaug2016ii
1
answer
34
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

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

86
views
1
answer
36
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
1
answer
37
VirtualGate 2015 TOC: Regular language FirstThirds
commented
Sep 19, 2016
in
Theory of Computation

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

198
views
virtualgate
theoryofcomputation
regularlanguage
regularset
2
answers
39
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

99
views
digitallogic
1
answer
40
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

116
views
22,195
questions
28,249
answers
63,693
comments
24,385
users