Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for theory
19
votes
3
answers
1
How to construct an automata with even number of a's and odd number of b's?
The alphabets are a and b. Construct a DFA
The alphabets are a and b.Construct a DFA
Gourab_Classic
109k
views
Gourab_Classic
asked
Mar 14, 2016
Theory of Computation
minimal-state-automata
theory-of-computation
finite-automata
combinatory
+
–
60
votes
10
answers
2
GATE CSE 2003 | Question: 36
How many perfect matching are there in a complete graph of $6$ vertices? $15$ $24$ $30$ $60$
How many perfect matching are there in a complete graph of $6$ vertices?$15$$24$$30$$60$
Kathleen
50.4k
views
Kathleen
asked
Sep 16, 2014
Graph Theory
gatecse-2003
graph-theory
graph-matching
normal
+
–
113
votes
9
answers
3
GATE CSE 2012 | Question: 38
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to$15$$30$$90$$36...
gatecse
35.0k
views
gatecse
asked
Sep 12, 2014
Graph Theory
gatecse-2012
graph-theory
normal
marks-to-all
counting
+
–
64
votes
8
answers
4
GATE CSE 1997 | Question: 6.4
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring? $0^*(1+0)^*$ $0^*1010^*$ $0^*1^*01^*$ $0^*(10+1)^*$
Which one of the following regular expressions over $\{0,1\}$ denotes the set of all strings not containing $\text{100}$ as substring?$0^*(1+0)^*$$0^*1010^*$$0^*1^*01^*$$...
Kathleen
37.5k
views
Kathleen
asked
Sep 29, 2014
Theory of Computation
gate1997
theory-of-computation
regular-expression
normal
+
–
77
votes
12
answers
5
GATE CSE 1994 | Question: 1.6, ISRO2008-29
The number of distinct simple graphs with up to three nodes is $15$ $10$ $7$ $9$
The number of distinct simple graphs with up to three nodes is$15$$10$$7$$9$
Kathleen
34.8k
views
Kathleen
asked
Oct 4, 2014
Graph Theory
gate1994
graph-theory
graph-connectivity
combinatory
normal
isro2008
counting
+
–
108
votes
7
answers
6
GATE CSE 2016 Set 2 | Question: 44
Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$ ... not recursive $L_{1}, L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursive
Consider the following languages.$L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2016 steps on some input} \right\}$,$L_{2} = \left\{\left\langl...
Akash Kanase
33.5k
views
Akash Kanase
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set2
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
5
votes
4
answers
7
Difference between DPDA and NPDA?
Amit Sharma
38.9k
views
Amit Sharma
asked
Jun 1, 2016
Theory of Computation
theory-of-computation
pushdown-automata
+
–
77
votes
12
answers
8
GATE CSE 2017 Set 2 | Question: 39
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$ ... $\emptyset$ $\{q_0, q_1, q_3\}$ $\{q_0, q_1, q_2\}$ $\{q_0, q_2, q_3 \}$
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...
Arjun
28.4k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set2
theory-of-computation
finite-automata
+
–
101
votes
10
answers
9
GATE CSE 2014 Set 1 | Question: 51
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $(a,b)$ and $(c,d)$ if $|a-c| \leq 1$ and $|b-d| \leq 1$. The number of edges in this graph is______.
Consider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j) \mid1 \leq i \leq 12, 1 \leq j \leq 12\}$. There is an edge between $...
go_editor
26.8k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set1
graph-theory
numerical-answers
normal
graph-connectivity
+
–
54
votes
15
answers
10
GATE CSE 2017 Set 1 | Question: 22
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ___________ .
Consider the language $L$ given by the regular expression $(a+b)^{*} b (a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-...
Arjun
29.3k
views
Arjun
asked
Feb 14, 2017
Theory of Computation
gatecse-2017-set1
theory-of-computation
finite-automata
numerical-answers
minimal-state-automata
+
–
50
votes
6
answers
11
GATE CSE 2019 | Question: 15
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping length (the constant guaranteed by the pumping lemma) for $L$ ? $3$ $5$ $9$ $24$
For $\Sigma = \{a ,b \}$, let us consider the regular language $L=\{x \mid x = a^{2+3k} \text{ or } x=b^{10+12k}, k \geq 0\}$. Which one of the following can be a pumping...
Arjun
34.2k
views
Arjun
asked
Feb 7, 2019
Theory of Computation
gatecse-2019
theory-of-computation
pumping-lemma
1-mark
+
–
93
votes
8
answers
12
GATE CSE 2006 | Question: 34
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is: $3$ $5$ $8$ $9$
Consider the regular language $L=(111+11111)^{*}.$ The minimum number of states in any DFA accepting this languages is:$3$$5$$8$$9$
Rucha Shelke
34.3k
views
Rucha Shelke
asked
Sep 22, 2014
Theory of Computation
gatecse-2006
theory-of-computation
finite-automata
normal
minimal-state-automata
+
–
59
votes
8
answers
13
GATE CSE 2016 Set 1 | Question: 42
Consider the following context-free grammars; $G_1 : S \to aS \mid B, B \to b \mid bB$ $G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$ Which one of the following pairs of languages is generated by $G_1$ and $G_2$ ... $\{ a^mb^n \mid m > 0 \text{ or } n>0\}$
Consider the following context-free grammars;$G_1 : S \to aS \mid B, B \to b \mid bB$$G_2 : S \to aA \mid bB, A \to aA \mid B \mid \varepsilon,B \to bB \mid \varepsilon$W...
Sandeep Singh
26.8k
views
Sandeep Singh
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set1
theory-of-computation
context-free-language
normal
+
–
39
votes
9
answers
14
GATE CSE 2014 Set 2 | Question: 3
The maximum number of edges in a bipartite graph on $12$ vertices is____
The maximum number of edges in a bipartite graph on $12$ vertices is____
go_editor
27.1k
views
go_editor
asked
Sep 28, 2014
Graph Theory
gatecse-2014-set2
graph-theory
graph-connectivity
numerical-answers
normal
+
–
83
votes
4
answers
15
GATE CSE 2015 Set 1 | Question: 51
Consider the NPDA ... follows: Which one of the following sequences must follow the string $101100$ so that the overall string is accepted by the automaton? $10110$ $10010$ $01010$ $01001$
Consider the NPDA $$ \left \langle Q= \left \{ q_{0}, q_{1}, q_{2} \right \},\Sigma = \left \{ 0, 1 \right \}, \Gamma = \left \{ 0, 1, \perp \right \}, \delta, q_{0}, \p...
makhdoom ghaya
23.8k
views
makhdoom ghaya
asked
Feb 13, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
pushdown-automata
normal
+
–
65
votes
9
answers
16
GATE CSE 2016 Set 1 | Question: 38
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$ ... integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &...
Sandeep Singh
24.0k
views
Sandeep Singh
asked
Feb 12, 2016
DS
gatecse-2016-set1
data-structures
graph-theory
normal
numerical-answers
+
–
29
votes
7
answers
17
GATE CSE 2020 | Question: 10
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements. $L$ is deterministic context-free. $L$ is context-free but not deterministic context-free. $L$ is not $LL(k)$ for any $k$. Which of the above statements is/are TRUE? Ⅰ only Ⅱ only Ⅰ and Ⅲ only Ⅲ only
Consider the language $L = \{a^{n}\mid n \geq 0\} \cup \{a^{n}b^{n}\mid n \geq 0\}$ and the following statements.$L$ is deterministic context-free.$L$ is context-free but...
Arjun
20.1k
views
Arjun
asked
Feb 12, 2020
Theory of Computation
gatecse-2020
theory-of-computation
identify-class-language
1-mark
+
–
33
votes
14
answers
18
GATE CSE 2019 | Question: 12
Let $G$ be an undirected complete graph on $n$ vertices, where $n > 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to $n!$ $(n-1)!$ $1$ $\frac{(n-1)!}{2}$
Let $G$ be an undirected complete graph on $n$ vertices, where $n 2$. Then, the number of different Hamiltonian cycles in $G$ is equal to$n!$$(n-1)!$$1$$\frac{(n-1)!}{2}...
Arjun
21.3k
views
Arjun
asked
Feb 7, 2019
Graph Theory
gatecse-2019
engineering-mathematics
discrete-mathematics
graph-theory
graph-connectivity
1-mark
+
–
34
votes
6
answers
19
GATE CSE 1996 | Question: 1.4
Which of the following statements is FALSE? The set of rational numbers is an abelian group under addition The set of integers in an abelian group under addition The set of rational numbers form an abelian group under multiplication The set of real numbers excluding zero is an abelian group under multiplication
Which of the following statements is FALSE?The set of rational numbers is an abelian group under additionThe set of integers in an abelian group under additionThe set of ...
Kathleen
23.0k
views
Kathleen
asked
Oct 9, 2014
Set Theory & Algebra
gate1996
set-theory&algebra
group-theory
normal
+
–
33
votes
9
answers
20
GATE CSE 2015 Set 1 | Question: 54
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
Let G be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in G is_______________.
makhdoom ghaya
24.6k
views
makhdoom ghaya
asked
Feb 13, 2015
Graph Theory
gatecse-2015-set1
graph-theory
graph-connectivity
normal
graph-planarity
numerical-answers
+
–
Page:
1
2
3
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register