Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
rballiwal
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Recent activity by rballiwal
2
answers
1
#GRAPH THEORY
A simple regular graph n vertices and 24 edges, find all possible values of n.
A simple regular graph n vertices and 24 edges, find all possible values of n.
2.6k
views
answered
Jun 4, 2019
Graph Theory
graph-theory
+
–
2
answers
2
GateForum Question Bank :Graph Theory
What is the probability that there is an edge in an undirected random graph having 8 vertices? 1 1/8
What is the probability that there is an edge in an undirected random graph having 8 vertices?1 1/8
2.1k
views
answer edited
Jun 4, 2019
Graph Theory
graph-theory
discrete-mathematics
+
–
2
answers
3
self doubt
What is the general formula for number of simple graph having n unlabelled vertices ??
What is the general formula for number of simple graph having n unlabelled vertices ??
1.3k
views
answered
Jun 4, 2019
Graph Theory
simple-graph
+
–
1
answer
4
self-doubt
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) . A walk in which no edges are repeated is called a trial. A trial in which no vertices are repeated is called a path. A trial in which only the starting and ending vertices are repeated is called a circuit. Are the definitions correct??
A graph with alternating edges and vertices is called a walk (we can repeat the number of vertices and edges any number of times) .A walk in which no edges are repeated ...
647
views
answered
Jun 4, 2019
Graph Theory
graph-theory
+
–
3
answers
5
UGC NET CSE | December 2018 | Part 2 | Question: 31
Let $r=a(a+b)^*, \: s=aa^*b$ and $t=a^*b$ be three regular expressions. Consider the following : $L(s) \subseteq L(r )\text{ and } L(s) \subseteq L(t)$ ... Choose the correct answer from the code given below : Only i is correct Only ii is correct Both i and ii are correct Neither i nor ii is correct
Let $r=a(a+b)^*, \: s=aa^*b$ and $t=a^*b$ be three regular expressions.Consider the following :$L(s) \subseteq L(r )\text{ and } L(s) \subseteq L(t)$$L(r ) \subseteq L(s)...
1.3k
views
comment edited
Dec 30, 2018
Unknown Category
ugcnetcse-dec2018-paper2
+
–
1
answer
6
SELF DOUBT_ RICE THEOREM
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }. is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
L = {<M1, M2>M1 and M2 are two TMs, and ε ∈ L(M1) \ L(M2) }.is it RECURSIVE OR RECURSIVE ENUMERABLE OR NOT EVEN RECURSIVE ENUM.
885
views
commented
Dec 30, 2018
Theory of Computation
rice-theorem
recursive-and-recursively-enumerable-languages
+
–
1
answer
7
regular expression for mod 3 =1
someone can help me found the regular expression of L={σ×w, σϵ∑={a, b},#σ(w)mod 3 = 1} tnx.
someone can help me found the regular expression ofL={σ×w, σϵ∑={a, b},#σ(w)mod 3 = 1} tnx.
2.8k
views
answered
Dec 30, 2018
Theory of Computation
regular-expression
+
–
1
answer
8
DFA doubt
let M be a DFA {a,b} with exactly 2 state .Suppose further that M accepts a finite number n of distinct words .what is the maximum value of n? a)1 b)2 c)3 d)4 e)there not fixed
let M be a DFA {a,b} with exactly 2 state .Suppose further that M accepts a finite number n of distinct words .what is the maximum value of n?a)1b)2c)3d)4e)there not fixe...
848
views
answered
Dec 30, 2018
1
answer
9
Madeasy test series
Does equivalence of CFG decidable ? That is for two CFG G1 and G2 L(G1)= L(G2)? And if it is DCFG than is it decidable.
Does equivalence of CFG decidable ?That is for two CFG G1 and G2 L(G1)= L(G2)?And if it is DCFG than is it decidable.
496
views
answered
Dec 30, 2018
Theory of Computation
decidability
theory-of-computation
context-free-language
recursive-and-recursively-enumerable-languages
+
–
8
answers
10
UGC NET CSE | June 2016 | Part 3 | Question: 55
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation $R_M$ defined by M as all states that are reachable from the start state. $R_M$ has ___ equivalence classes. 2 4 5 6
Let L be the language generated by regular expression 0*10* and accepted by the deterministic finite automata M. Consider the relation $R_M$ defined by M as all states th...
7.2k
views
commented
Dec 30, 2018
Theory of Computation
ugcnetcse-june2016-paper3
theory-of-computation
regular-expression
regular-language
+
–
0
answers
11
decidablilty
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know. If a language is an REL (recursive enumerable ... recursive or not *undecidable*. Hence, recursive languages should be undecidable-which they are not! What is wrong with the above reasoning?
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be cor...
276
views
commented
Dec 25, 2018
Theory of Computation
finite-automata
turing-machine
+
–
0
answers
12
Rice theorem
1.{<M>| M is a TM accepts any string starting with 1} 2.{<M>| M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem. for 1. Is Tyes = { string starting with 1} Tno = { all strings – strings starting with 1} what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
1.{<M>| M is a TM accepts any string starting with 1}2.{<M>| M is TM accept exactly 20 strings} Please guide I don’t know how to apply rice theorem.for 1. Is Tyes = { s...
589
views
commented
Dec 17, 2018
Theory of Computation
rice-theorem
decidability
+
–
1
answer
13
Self doubt
Unrestricted grammar generate Recursive enumerable language. Am i right??
Unrestricted grammar generate Recursive enumerable language.Am i right??
258
views
commented
Dec 17, 2018
1
answer
14
Zeal Theory of Computation module.
Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
Does the statement given below is true?If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
588
views
commented
Dec 17, 2018
Theory of Computation
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
1
answer
15
Self Doubt regarding Type 1
L= a*b* Grammar associated with this language is a Type 3 S---> aS/A A--->bA/€ Now we know that Type 1 Grammar is Non Contracting Grammar Here A---> € is a Contracting production And only S---> € is allowed in Type 1 And if a grammar is not type 1 how it can be type 3 ? Please help
L= a*b*Grammar associated with this language is a Type 3S - aS/AA ->bA/€Now we know that Type 1 Grammar is Non Contracting GrammarHere A - € is a Contracting producti...
291
views
commented
Dec 17, 2018
1
answer
16
self doubt - Turing Machines
I have doubt in the following question: Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by CFG G. Let L(M) be the language accepted by a turing machine M. Now, I am getting confused over the keyword “accepted”. What should L(M) be considered? Is it REC or RE?
I have doubt in the following question:Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by CFG G. Let L(M) be the language...
302
views
answered
Dec 17, 2018
Theory of Computation
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
answer
17
Turing Machine lecture content stan..
A = { <M,w> | M is a TM that accepts W} what is A’( A complement)? Pls guide : M is a Tm doesn,t accept w, Unable to approach further Source:https://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/20/Small20.pdf
A = { <M,w | M is a TM that accepts W}what is A’( A complement)? Pls guide : M is a Tm doesn,t accept w, Unable to approach further Source:https://web.stanford.edu/c...
297
views
commented
Dec 16, 2018
Theory of Computation
turing-machine
decidability
+
–
0
answers
18
MadeEasy Theorybook: Theory of Computation - Context Free Languages
According to the given formula above, how many productions should be there ? S-->aAbB A-->aA | a B-->bB | b According to me., it should be 17 but in the book answer is 9, can anyone tell me how? mage widget
According to the given formula above, how many productions should be there ? S >aAbBA >aA | aB >bB | bAccording to me., it should be 17 but in the book answer is 9, can a...
475
views
commented
Dec 16, 2018
Theory of Computation
theory-of-computation
context-free-language
self-doubt
made-easy-booklet
+
–
1
answer
19
Question on P problem
I think answer should be D. they have given wrong answer. Please correct me if I am wrong.
I think answer should be D. they have given wrong answer.Please correct me if I am wrong.
335
views
answered
Dec 16, 2018
Theory of Computation
theory-of-computation
+
–
1
answer
20
Context free language Question
please provide solution for given quesion.
please provide solution for given quesion.
274
views
answered
Dec 16, 2018
Theory of Computation
context-free-language
theory-of-computation
+
–
2
answers
21
pushdown automata
What is the difference between DPDA which accept Language by the empty stack and the one which accepts by final state
What is the difference between DPDA which accept Language by the empty stack and the one which accepts by final state
517
views
answered
Dec 16, 2018
3
answers
22
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
1.7k
views
answered
Dec 16, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
theory-of-computation
turing-machine
rice-theorem
+
–
2
answers
23
toc concept
do recursive language is recursively enumerable as well ? true or false
do recursive language is recursively enumerable as well ? true or false
306
views
commented
Dec 15, 2018
4
answers
24
Question of regular expression
Consider the following regular expressions : (i) ($(a/b)^{*}$ (ii) $(a^{*}/b^{*})^{*}$ (iii) $((\epsilon /a)b^{*})^{*}$ Which of the following statements are correct ? (a) (i) ,(ii) are equal and (ii) , (iii) are not . (b) (i) ,(ii) are equal and ( ... me (a)* . Isn't it so ? From (i) ($(a/b)^{*}$ : I can not separate a and b . So , how can they all be equal ?
Consider the following regular expressions :(i) ($(a/b)^{*}$ (ii) $(a^{*}/b^{*})^{*}$ (iii) $((\epsilon /a)b^{*})^{*}$Which of the following statements are correct ?...
6.2k
views
commented
Dec 15, 2018
Theory of Computation
theory-of-computation
regular-expression
+
–
2
answers
25
recursive language
Can a language exist which is undecidable as well as Recursive language ? If yes please give example.
Can a language exist which is undecidable as well as Recursive language ? If yes please give example.
946
views
answer edited
Dec 15, 2018
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
2
answers
26
DFA doubt
DFA in which 01 and 10 have equal number of occurrences
DFA in which 01 and 10 have equal number of occurrences
1.5k
views
answer edited
Dec 14, 2018
Theory of Computation
finite-automata
theory-of-computation
+
–
2
answers
27
Minimal DFA
Given following NFA find the minimal equivalent DFA
Given following NFAfind the minimal equivalent DFA
1.5k
views
commented
Dec 14, 2018
Theory of Computation
theory-of-computation
minimal-state-automata
number-of-states
finite-automata
+
–
1
answer
28
CONVERT CFG TO GNF
S→ AB A→ BS|b B→ SA|a INTO GNF
S→ ABA→ BS|bB→ SA|a INTO GNF
26.1k
views
commented
Dec 14, 2018
Theory of Computation
gnf
conjunctive-normal-form
theory-of-computation
context-free-language
+
–
2
answers
29
Countable set
If power set of natural number is uncountable , and that is why non RE, then how is it possible set of natural number is countable and RE?------give some reason
If power set of natural number is uncountable , and that is why non RE,then how is it possible set of natural number is countable and RE? give some reason
752
views
answered
Dec 14, 2018
Theory of Computation
theory-of-computation
+
–
2
answers
30
Turing Machine-Techtud
If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine $A)$ Regular Language $B)$ CFL $C)$ CSL $D)$ None Ans given CSL but I thought it should be regular then what is difference between input restricted and constant size tape? https://gateoverflow.in/26653/gate1991-17-a Plz confirm what is correct?
If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine $A)$ Regular Language$B)$ CFL$C)$ CSL$D)$ NoneAns given CSL b...
1.4k
views
answer edited
Dec 14, 2018
Theory of Computation
turing-machine
theory-of-computation
+
–
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register