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
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
6 hours
ago
in
Theory of Computation

918
views
gate2011
theoryofcomputation
finiteautomata
normal
1
answer
2
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
7 hours
ago
in
Theory of Computation

51
views
theoryofcomputation
regularlanguages
2
answers
3
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
10 hours
ago
in
Theory of Computation

26
views
theoryofcomputation
regularlanguages
1
answer
4
Why this is not a regular language?
commented
1 day
ago
in
Theory of Computation

407
views
theoryofcomputation
regularlanguages
identifyclasslanguage
3
answers
5
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
1 day
ago
in
Digital Logic

1.2k
views
gate2004
digitallogic
circuitoutput
normal
2
answers
6
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
1 day
ago
in
Theory of Computation

696
views
gate2008it
theoryofcomputation
finiteautomata
normal
3
answers
7
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
3 days
ago
in
Theory of Computation

790
views
gate2007it
theoryofcomputation
finiteautomata
normal
1
answer
8
Context Free Languages
{${a^{i}b^{j}c^{k} (i\leq j)or(j\leq i),j=k}$} is CFL?
answer selected
3 days
ago
in
Theory of Computation

23
views
1
answer
9
Generate CFG
What will be the CFG when w$\in$(a,b)* where w contains at least 3 a's?
answer selected
4 days
ago
in
Theory of Computation

24
views
theoryofcomputation
contextfreelanguage
7
answers
10
GATE 2016143
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
6 days
ago
in
Theory of Computation

2.5k
views
gate20161
theoryofcomputation
pushdownautomata
normal
0
answers
11
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

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

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

44
views
digitallogic
2
answers
14
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

303
views
gate1996
theoryofcomputation
contextfreelanguage
easy
4
answers
15
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

104
views
theoryofcomputation
minimalstateautomata
dfa
finiteautomata
1
answer
16
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

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

89
views
digitallogic
2
answers
18
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

662
views
gate1998
theoryofcomputation
finiteautomata
normal
4
answers
19
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

803
views
gate2007it
theoryofcomputation
finiteautomata
normal
1
answer
20
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

601
views
gate1998
theoryofcomputation
finiteautomata
normal
3
answers
21
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

933
views
gate2003
theoryofcomputation
finiteautomata
normal
2
answers
22
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

47
views
4
answers
23
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

995
views
gate20143
theoryofcomputation
regularexpressions
numericalanswers
easy
3
answers
24
GATE1999_1.4
Consider the regular expression $(0 + 1) (0+1) \dots N$ times. The minimum state finite automaton that recognizes the language represented by this regular expression contains $n$ states $n+1$ states $n+2$ states None of the above
commented
Aug 10
in
Theory of Computation

1.2k
views
gate1999
theoryofcomputation
finiteautomata
easy
2
answers
25
Boolean expression hazards
Which of the following expression remove hazard from : $xy+zx'$? A. $xy+zx'$ B. $xy+zx'+wyz$ C. $xy+zx'+yz$ D. $xy+zx'+wz$
commented
Aug 10
in
Digital Logic

527
views
digitallogic
digital
booleanexpressions
statichazard
1
answer
26
GATE2007IT48
Consider the grammar given below S → x B  y A A → x  x S  y A A B → y  y S  x B B Consider the following strings. xxyyx xxyyxy xyxy yxxy yxx xyx Which of the above strings are generated by the grammar ? i, ii and iii ii, v and vi ii, iii and iv i, iii and iv
commented
Aug 9
in
Theory of Computation

578
views
gate2007it
theoryofcomputation
contextfreelanguage
normal
2
answers
27
GATE2008IT32
If the final states and nonfinal states in the DFA below are interchanged, then which of the following languages over the alphabet {a, b} will be accepted by the new DFA? Set of all strings that do not end with ab Set of all strings ... b Set of all strings that do not contain the substring ab, The set described by the regular expression b*aa*(ba)*b*
commented
Aug 9
in
Theory of Computation

698
views
gate2008it
theoryofcomputation
finiteautomata
normal
4
answers
28
GATE20082
If $P, Q, R$ are subsets of the universal set U, then $$(P\cap Q\cap R) \cup (P^c \cap Q \cap R) \cup Q^c \cup R^c$$ is $Q^c \cup R^c$ $P \cup Q^c \cup R^c$ $P^c \cup Q^c \cup R^c$ U
commented
Aug 8
in
Set Theory & Algebra

490
views
gate2008
normal
settheory&algebra
sets
1
answer
29
Made Easy Question Bank Page#407, Q# 16
commented
Aug 4
in
Digital Logic

186
views
digitallogic
booleanexpressions
2
answers
30
an introduction to formal languages (peter linz) chapter2..excercise ..7th (d)
answer selected
Jul 28
in
Theory of Computation

33
views
1
answer
31
Why L = { w x w ∣ w , x ∈ ( a + b ) + } is not regular?
commented
Jul 26
in
Theory of Computation

42
views
theoryofcomputation
regularlanguages
decidability
1
answer
32
cyk algorithm is used for CFG'S to test which class of problem???
commented
Jul 25
in
Theory of Computation

198
views
cykalgorithm
3
answers
33
TIFR2014B12
Consider the following three statements: (i) Intersection of infinitely many regular languages must be regular. (ii) Every subset of a regular language is regular. (iii) If $L$ is regular and $M$ is not regular then $L ∙ M$ is necessarily not regular. ... ? true, false, true. false, false, true. true, false, true. false, false, false. true, true, true.
commented
Jul 18
in
Theory of Computation

564
views
tifr2014
theoryofcomputation
regularlanguages
1
answer
34
GATE1999_7
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.
commented
Jul 15
in
Theory of Computation

282
views
gate1999
theoryofcomputation
contextfreelanguage
normal
1
answer
35
GATE199816
Design a synchronous counter to go through the following states: $$1, 4, 2, 3, 1, 4, 2, 3, 1, 4 \dots $$
commented
Jun 29
in
Digital Logic

227
views
gate1998
digitallogic
normal
descriptive
synchronouscounter
4
answers
36
GATE2014AE6
Find the odd one in the following group: $ALRVX$,$EPVZB$,$ITZDF$,$OYEIK$ A). $ALRVX$ B). $EPVZB$ C). $ITZDF$ D). $OYEIK$
answer selected
Jun 2
in
Verbal Ability

167
views
gate2014ae
oddone
verbalreasoning
verbalability
2
answers
37
ISRO20178
Which symbol denote derived attributes in ER Model? Double ellipse Dashed ellipse Squared ellipse Ellipse with attribute name underlined
answer selected
May 8
in
Databases

1.1k
views
isro2017
databases
erdiagram
4
answers
38
ISRO201775
Choose the most appropriate HTML tag in the following to create a numbered list <dl> <list> <ul> <ol>
answer selected
May 8
in
Web Technologies

820
views
isro2017
webtechnologies
html
nongate
5
answers
39
GATE20095, ISRO201757
$(1217)_8$ is equivalent to $(1217)_{16}$ $(028F)_{16}$ $(2297)_{10}$ $(0B17)_{16}$
answer selected
May 7
in
Digital Logic

554
views
gate2009
digitallogic
numberrepresentation
isro2017
2
answers
40
ISRO201758
Which of the following is not a life cycle model? Spiral model Prototyping model Waterfall model Capability maturity model
answer selected
May 7
in
IS&Software Engineering

972
views
isro2017
is&softwareengg
nongate
25,032
questions
32,178
answers
74,989
comments
30,215
users