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
3
answers
1
GATE2006IT5
Which regular expression best describes the language accepted by the nondeterministic automaton below? (a + b)* a(a + b)b (abb)* (a + b)* a(a + b)* b(a + b)* (a + b)*
commented
Oct 13
in
Theory of Computation

335
views
gate2006it
theoryofcomputation
regularexpressions
normal
2
answers
2
Regular/Nonregular Language
Consider the following subsets of $\left\{a, b, \$ \right\}^*$ $A=\left\{xy\, \, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\},$ $B=\left\{x\$y\, \, x,y\in\left\{a,b\right\}^*,\#a(x)=\#b(y)\right\}$ ... ? (A) $A$ and $B$ both are regular (B) $A$ is regular but $B$ is not (C) $A$ is not regular but $B$ is regular (D) Both are nonregular
commented
Oct 13
in
Theory of Computation

471
views
regularlanguages
theoryofcomputation
virtualgate
testseries
2
answers
3
TIFR2015B10
Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$ $L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \leq 10\right\}$ State which ... regular. $L_{1}$ is regular and $L_{2}$ is not regular. $L_{1}$ is not regular and $L_{2}$ is regular. Both $L_{1}$ and $L_{2}$ are infinite.
commented
Sep 25
in
Theory of Computation

310
views
tifr2015
regularlanguages
2
answers
4
GATE2013_33
Consider the DFA A given below. Which of the following are FALSE? Complement of $L(A)$ is contextfree. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*) $ For the language accepted by A, A is the minimal DFA. A accepts all strings over {0, 1} of length at least 2. (A) 1 and 3 only (B) 2 and 4 only (C) 2 and 3 only (D) 3 and 4 only
commented
Sep 25
in
Theory of Computation

1.1k
views
gate2013
theoryofcomputation
finiteautomata
normal
1
answer
5
testseries
commented
Sep 25
in
Theory of Computation

61
views
theoryofcomputation
1
answer
6
ME_Test_Series_DLD_Question  All the logic gates in the circuit shown below have finite propagation delay.
commented
Sep 25
in
Digital Logic

294
views
madeeasytestseries
testseries
digitallogic
2
answers
7
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
Sep 24
in
Theory of Computation

379
views
gate2007it
theoryofcomputation
normal
contextfreelanguage
3
answers
8
GATE20008
A push down automation (pda) is given in the following extended notation of finite state diagram: The nodes denote the states while the edges denote the moves of the pda. The edge labels are of the form d, s/s' where d is the input symbol read and s, s ... above notation that accept the language $\left\{0^{n}1^{m} \mid n \leq m \leq 2n\right\}$ by empty stack
commented
Sep 24
in
Theory of Computation

522
views
gate2000
theoryofcomputation
descriptive
pushdownautomata
2
answers
9
GATE2006IT3
In the automaton below, s is the start state and t is the only final state. Consider the strings u = abbaba, v = bab, and w = aabb. Which of the following statements is true? The automaton accepts u and v but not w The automaton accepts each of u, v, and w The automaton rejects each of u, v, and w The automaton accepts u but rejects v and w
commented
Sep 24
in
Theory of Computation

307
views
gate2006it
theoryofcomputation
finiteautomata
normal
2
answers
10
whether the following languages are DCFL or not???
commented
Sep 22
in
Theory of Computation

360
views
theoryofcomputation
dcfl
1
answer
11
ISRO201330
In a three stage counter, using RS flip flops what will be the value of the counter after giving $9$ pulses to its input? Assume that the value of counter before giving any pulses is 1. 1 2 9 10
commented
Sep 19
in
Digital Logic

1.2k
views
isro2013
digitallogic
flipflop
2
answers
12
GATE199816
Design a synchronous counter to go through the following states: $$1, 4, 2, 3, 1, 4, 2, 3, 1, 4 \dots $$
commented
Sep 16
in
Digital Logic

306
views
gate1998
digitallogic
normal
descriptive
synchronouscounter
6
answers
13
GATE1991_17,b
Let $L$ be the language of all binary strings in which the third symbol from the right is a $1$. Give a nondeterministic finite automaton that recognizes $L$. How many states does the minimized equivalent deterministic finite automaton have? Justify your answer briefly?
commented
Sep 8
in
Theory of Computation

1k
views
gate1991
theoryofcomputation
finiteautomata
normal
2
answers
14
CFG
Why is S2 not a correct option?
commented
Aug 30
in
Theory of Computation

117
views
1
answer
15
Inherently ambiguous grammar
Q Which one of following languages is inherently ambiguous? (A) The set of all strings of the form $\left\{a^nb^n,n>0 \right\}$ (B) $\left\{a^nb^nc^md^m,n,m>0 \right\}$ (C) $\left\{a^nb^nc^md^m,n,m> ... Both (B) and (C) Plz explain.. ..........Is there any criteria on the basis of which we could identify inherently ambiguous grammar
commented
Aug 29
in
Theory of Computation

1.8k
views
theoryofcomputation
inherentlyambiguous
1
answer
16
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 ... 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
Aug 28
in
Theory of Computation

669
views
gate2006
theoryofcomputation
normal
identifyclasslanguage
2
answers
17
GATE2008IT36
Consider the following two finite automata. M1 accepts L1 and M2 accepts L2. Which one of the following is TRUE? L1 = L2 L1 ⊂ L2 L1 ∩ L2' = ∅ L1 ∪ L2 ≠ L1
commented
Aug 28
in
Theory of Computation

908
views
gate2008it
theoryofcomputation
finiteautomata
normal
3
answers
18
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 λ denote transitions on the empty string.
commented
Aug 24
in
Theory of Computation

986
views
gate2007it
theoryofcomputation
finiteautomata
normal
2
answers
19
GATE2014116
Consider the finite automaton in the following figure: What is the set of reachable states for the input string 0011? {$q_0,q_1,q_2$} {$q_0,q_1$} {$q_0,q_1,q_2,q_3$} {$q_3$}
commented
Aug 24
in
Theory of Computation

610
views
gate20141
theoryofcomputation
finiteautomata
easy
3
answers
20
GATE200461
Consider the partial implementation of a 2bit counter using T flipflops following the sequence 02310, as shown below. To complete the circuit, the input X should be $Q_2^c$ $Q_2 + Q_1$ $\left(Q_1 + Q_2\right)^c$ $Q_1 \oplus Q_2$
commented
Aug 23
in
Digital Logic

1.4k
views
gate2004
digitallogic
circuitoutput
normal
1
answer
21
GATE2011_42
Definition of a language $L$ with alphabet $\{a\}$ is given as following. $$ L = \left\{a^{nk} \mid k > 0, \:\: and \:\: n \text{ is a positive integer constant} \right\}$$ What is the minimum number of states needed in a DFA to recognize $L$? (A) $k+1$ (B) $n+1$ (C) $2^{n+1}$ (D) $2^{k+1}$
commented
Aug 22
in
Theory of Computation

1.2k
views
gate2011
theoryofcomputation
finiteautomata
normal
1
answer
22
Regular Languages
Choose the correct statement: a) For every regular language, there is right linear and left linear grammar. b) For every regular language, there is right linear or left linear grammar but not both. c) Transpose of a regular language is regular. d) both a and c
commented
Aug 22
in
Theory of Computation

63
views
theoryofcomputation
regularlanguages
2
answers
23
Regular Languages
Let A = {a, b}, L = {a^nb^n:n>=1} and R = A*, then the languages RUL and R are: a) Regular, Regular b) Regular, Not Regular c) Not Regular, Regular d) Not Regular, Not Regular
answer selected
Aug 22
in
Theory of Computation

42
views
theoryofcomputation
regularlanguages
1
answer
24
Why this is not a regular language?
commented
Aug 21
in
Theory of Computation

430
views
theoryofcomputation
regularlanguages
identifyclasslanguage
1
answer
25
Context Free Languages
{${a^{i}b^{j}c^{k} (i\leq j)or(j\leq i),j=k}$} is CFL?
answer selected
Aug 19
in
Theory of Computation

34
views
1
answer
26
Generate CFG
What will be the CFG when w$\in$(a,b)* where w contains at least 3 a's?
answer selected
Aug 18
in
Theory of Computation

36
views
theoryofcomputation
contextfreelanguage
7
answers
27
GATE2016143
Consider the transition diagram of a PDA given below with input alphabet $\Sigma=\{a,b\}$ and stack alphabet $\Gamma = \{X,Z\}$. $Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA Which one of the following is TRUE? $L =\{a ... input $L =\{a^n\mid n \geq0 \} \cup \{a^nb^n \mid n \geq 0\}$ and is deterministic contextfree
commented
Aug 16
in
Theory of Computation

2.7k
views
gate20161
theoryofcomputation
pushdownautomata
normal
0
answers
28
Dfa toc
construct a mininal DFA which accept sets of all strings over {a,b} such that 2nd symbol from RHS in each string is 'a'?
closed
Aug 15
in
Theory of Computation

23
views
dfa
1
answer
29
Degital
what is the minimum number of digits required to represent 3345(radix 10) in binary ?
answer selected
Aug 15
in
Digital Logic

38
views
digitallogic
1
answer
30
doubt
answer selected
Aug 15
in
Digital Logic

52
views
digitallogic
3
answers
31
GATE1996_2.8
If $L_1$ and $L_2$ are context free languages and $R$ a regular set, one of the languages below is not necessarily a context free language. Which one? $L_1.L_2$ $L_1 \cap L_2$ $L_1 \cap R$ $L_1 \cup L_2$
commented
Aug 15
in
Theory of Computation

423
views
gate1996
theoryofcomputation
contextfreelanguage
easy
4
answers
32
TOC Minimal DFA design
Let language defined is { Number of a's =2 and length of string is atleast 3} over alphabet {a,b}.What are number of states in minimal DFA?
answer selected
Aug 14
in
Theory of Computation

131
views
theoryofcomputation
minimalstateautomata
dfa
finiteautomata
1
answer
33
For even no a's RE (b*ab*ab*)* + b* correct or (b*ab*ab*)*.b* or both are equal
answered
Aug 14
in
Theory of Computation

85
views
theoryofcomputation
finiteautomata
regularexpressions
1
answer
34
Size of a output of combinational circuit
answer selected
Aug 14
in
Digital Logic

92
views
digitallogic
2
answers
35
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
Aug 14
in
Theory of Computation

836
views
gate1998
theoryofcomputation
finiteautomata
normal
4
answers
36
GATE2007IT50
Consider the following finite automata P and Q over the alphabet {a, b, c}. The start states are indicated by a double arrow and final states are indicated by a double circle. Let the languages recognized by them be denoted by L(P) and L(Q) respectively. The automation which recognizes the language L(P) ∩ L(Q) is :
commented
Aug 13
in
Theory of Computation

962
views
gate2007it
theoryofcomputation
finiteautomata
normal
1
answer
37
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
Aug 13
in
Theory of Computation

749
views
gate1998
theoryofcomputation
finiteautomata
normal
3
answers
38
GATE200355
Consider the NFA M shown below. Let the language accepted by M be L. Let $L_1$ be the language accepted by the NFA $M_1$ obtained by changing the accepting state of M to a nonaccepting state and by changing the nonaccepting states of M to accepting states. Which ... statements is true? $L_1 = \{0,1\}^*L$ $L_1 = \{0,1\}^*$ $L_1 \subseteq L$ $L_1 = L$
commented
Aug 13
in
Theory of Computation

1.1k
views
gate2003
theoryofcomputation
finiteautomata
normal
2
answers
39
Theory of computation
No of State for minimal DFA for empty language ? If your answer is 1 or 2 then please explain to support your answer
commented
Aug 11
in
Theory of Computation

55
views
4
answers
40
GATE2014315
The length of the shortest string NOT in the language (over $\Sigma = \{a, b\})$ of the following regular expression is _______. $$a^*b^*(ba)^*a^*$$
commented
Aug 11
in
Theory of Computation

1.2k
views
gate20143
theoryofcomputation
regularexpressions
numericalanswers
easy
27,339
questions
35,192
answers
84,203
comments
33,314
users