Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged recursive-and-recursively-enumerable-languages
0
votes
2
answers
211
TestBook Test Series: Theory Of Computation - Recursive and Recursively Enumerable Languages
thor
444
views
thor
asked
Nov 17, 2016
Theory of Computation
testbook-test-series
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
3
votes
1
answer
212
Ace Test Series: Theory Of Computation - Recursive And Recursively Enumerable Languages
Choose the correct statement: The set $[0,1]$ can be efficiently enumerated. The set of all formal languages can be efficiently enumerated. All real numbers can be efficiently enumerated. Set of all finite automata can be efficiently enumerated.
Choose the correct statement:The set $[0,1]$ can be efficiently enumerated.The set of all formal languages can be efficiently enumerated.All real numbers can be efficient...
thor
839
views
thor
asked
Nov 16, 2016
Theory of Computation
ace-test-series
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
3
votes
1
answer
213
Doubt - TOC
State True/False A subset of recursive language can be recursive enumerable that is not recursive. P.S : I don't know the answer.. but it should be false according to me.. Kindly let me know if i am wrong with an example ..
State True/FalseA subset of recursive language can be recursive enumerable that is not recursive. P.S : I don't know the answer.. but it should be false according to me.....
Gate Mission 1
486
views
Gate Mission 1
asked
Nov 7, 2016
Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
2
votes
0
answers
214
toc decidability
Which of the following statements regarding $L_1$ and $L_2$ is true? $L_1$ ={⟨M⟩ ∣ M has a state that is visited no more than 2017 times when started on an empty tape} $L_2$ ={⟨M⟩ ∣ M has a state that is visited at least 2017 times when ... L1 is decidable and L2 is undecidable. L1 is undecidable and L2 is decidable Both L1 and L2 are decidable. Both L1 and L2 are undecidable
Which of the following statements regarding $L_1$ and $L_2$ is true?$L_1$ ={⟨M⟩ ∣ M has a state that is visited no more than 2017 times when started on an empty tap...
Amit puri
844
views
Amit puri
asked
Oct 20, 2016
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
215
RECURSIVE & R.E.
Is L(M) context free language? Tell whether language is re or non re.
Is L(M) context free language?Tell whether language is re or non re.
Çșȇ ʛấẗẻ
302
views
Çșȇ ʛấẗẻ
asked
Sep 11, 2016
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
4
votes
2
answers
216
toc -recuresively ennumerable
Let L be a regular language, and R be a turing recognizable language but not acceptable language. Which of the following is possible? a) Set of strings common in L and R' can be in not RE(where ' is a complement operation) b)Set of strings common in L and R' can be recursive. 1) only a 2)only b 3) both 4) none
Let L be a regular language, and R be a turing recognizable language but not acceptable language. Which of the following is possible?a) Set of strings common in L and R' ...
resilientknight
1.0k
views
resilientknight
asked
Aug 2, 2016
Theory of Computation
recursive-and-recursively-enumerable-languages
theory-of-computation
+
–
2
votes
2
answers
217
Toc-Recursively Ennumerable
A is a decision problem. If A is recursively ennumerable then there exists an algorithm which halts on every string in A. True or false.Cite with reasons.
A is a decision problem. If A is recursively ennumerable then there exists an algorithm which halts on every string in A.True or false.Cite with reasons.
resilientknight
1.3k
views
resilientknight
asked
Aug 2, 2016
Theory of Computation
recursive-and-recursively-enumerable-languages
theory-of-computation
+
–
3
votes
2
answers
218
UGC NET CSE | Junet 2015 | Part 3 | Question: 62
Given the following two statements: $S_1$: If $L_1$ and $L_2$ are recursively enumerable languages over $\Sigma^*$, then $L_1 \cup L_2$ and $L_1 \cap L_2$ are also recursively enumerable. $S_2$: The set of recursively enumerable languages is ... not correct and $S_2$ is correct Both $S_1$ and $S_2$ are not correct Both $S_1$ and $S_2$ are correct
Given the following two statements:$S_1$: If $L_1$ and $L_2$ are recursively enumerable languages over $\Sigma^*$, then $L_1 \cup L_2$ and $L_1 \cap L_2$ are also recursi...
go_editor
2.0k
views
go_editor
asked
Aug 2, 2016
Theory of Computation
ugcnetcse-june2015-paper3
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
1
votes
2
answers
219
Relation between NP, recursive and recusive enumerable
I) Every language in NP is recursive. II)Every language in NP is recursively enumerable. Which of the statements is /are true? A. I only B. II only C. Both I and II D Neither I nor II
I) Every language in NP is recursive.II)Every language in NP is recursively enumerable.Which of the statements is /are true?A. I onlyB. II onlyC. Both I and IID Neither I...
sh!va
3.0k
views
sh!va
asked
Jul 12, 2016
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
–3
votes
1
answer
220
Toc Recursive and Recursive enumberable Language
geet.m
2.1k
views
geet.m
asked
Jun 29, 2016
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
6
votes
4
answers
221
ISRO2011-79
A problem whose language is recursion is called? Unified problem Boolean function Recursive problem Decidable
A problem whose language is recursion is called?Unified problemBoolean functionRecursive problemDecidable
go_editor
4.4k
views
go_editor
asked
Jun 24, 2016
Theory of Computation
isro2011
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
47
votes
5
answers
222
GATE CSE 2016 Set 1 | Question: 44
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$, and $Z$ reduces to $\overline{X}$ (reduction means the standard ... enumerable. $W$ is not recursively enumerable and $Z$ is recursive. $W$ is not recursively enumerable and $Z$ is not recursive.
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $\overline{Y}$ reduces to $W$,...
Sandeep Singh
12.4k
views
Sandeep Singh
asked
Feb 12, 2016
Theory of Computation
gatecse-2016-set1
theory-of-computation
easy
recursive-and-recursively-enumerable-languages
reduction
+
–
108
votes
7
answers
223
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
+
–
3
votes
1
answer
224
Complement of a recursive language
Given a TM M, complement of L(M) is context-free. True/False?
Given a TM M, complement of L(M) is context-free. True/False?
Arjun
4.0k
views
Arjun
asked
Jan 9, 2016
Theory of Computation
recursive-and-recursively-enumerable-languages
context-free-language
+
–
2
votes
1
answer
225
Turing Recognizable L
If $L$ is Turing-recongnizable. Then (A) $L$ and $\bar{L}$ must be decidable. (B) $L$ must be decidable but $\bar{L}$ need not be. (C) Either $L$ is decidable or $\bar{L}$ is not Turing recognizable. (D) None of above.
If $L$ is Turing-recongnizable. Then(A) $L$ and $\bar{L}$ must be decidable.(B) $L$ must be decidable but $\bar{L}$ need not be.(C) Either $L$ is decidable or $\bar{L}$ i...
bahirNaik
833
views
bahirNaik
asked
Jan 4, 2016
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
226
Two languages reducible to each other in polynomial time. Which is false option for them?
If Language L1 is reducible to L2 and L2 reducible to L1, then shouldn't they both be Recursively Enumerable Languages? I am really confused with the option given. Source : testbook.com live test on 3rd January, 2016
If Language L1 is reducible to L2 and L2 reducible to L1, then shouldn't they both be Recursively Enumerable Languages? I am really confused with the option given.Source ...
Utk
700
views
Utk
asked
Jan 4, 2016
Theory of Computation
recursive-and-recursively-enumerable-languages
normal
compound-automata
+
–
3
votes
1
answer
227
Please explain?
Consider the following Languages: $L_{ne}=\{\langle M \rangle \mid L(M)\neq \phi \}$ $L_{e}=\{\langle M \rangle \ \mid L(M)=\phi \}$ where $\langle M \rangle$ denotes encoding of a Turing Machine $M$ Then which of the following is true? (a) $L_{ne}$ is r.e. but not ... .e. (b) Both are not r.e. (c) Both are recursive (d) $L_{e}$ is r.e. but not recursive and $L_{ne}$ is not r.e.
Consider the following Languages:$L_{ne}=\{\langle M \rangle \mid L(M)\neq \phi \}$$L_{e}=\{\langle M \rangle \ \mid L(M)=\phi \}$where $\langle M \rangle$ denotes encodi...
Rajat Sharma 1
2.1k
views
Rajat Sharma 1
asked
Dec 15, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
rice-theorem
+
–
5
votes
1
answer
228
turing machine plzz xplain
Let $A=\{\langle M\rangle \mid M$ is turing machine that halts on all inputs and $L(M)=L'$ for some undecidable language $L'\}$. Then $A$ is ____ a. Regular language b. Recursive language but not regular c. Recursively enumerable language but not recursive language d. Non-recursively enumerable language
Let $A=\{\langle M\rangle \mid M$ is turing machine that halts on all inputs and $L(M)=L'$ for some undecidable language $L'\}$. Then $A$ is ____a. Regular language b. Re...
Jay Singh
819
views
Jay Singh
asked
Dec 6, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
24
votes
2
answers
229
TIFR CSE 2012 | Part B | Question: 19
Which of the following statements is TRUE? Every turning machine recognizable language is recursive. The complement of every recursively enumerable language is recursively enumerable. The complement of a recursive language is recursively enumerable. The ... . The set of turning machines which do not halt on empty input forms a recursively enumerable set.
Which of the following statements is TRUE?Every turning machine recognizable language is recursive.The complement of every recursively enumerable language is recursively ...
makhdoom ghaya
2.8k
views
makhdoom ghaya
asked
Nov 2, 2015
Theory of Computation
tifr2012
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
6
votes
1
answer
230
Which of the folowing are R.E
Which of the following problem(s) is/are Recursively enumerable or its complement is recursively enumerable? I. The language of all Turing machines that accept nothing. II. The language of all Turing machines that accept everything. III. The language of all CFG’s that are ambiguous.
Which of the following problem(s) is/are Recursively enumerable or its complement is recursively enumerable?I. The language of all Turing machines that accept nothing.II....
Mari Ganesh Kumar
2.0k
views
Mari Ganesh Kumar
asked
Oct 17, 2015
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
15
votes
1
answer
231
TIFR CSE 2010 | Part B | Question: 40
Which of the following statement is FALSE? All recursive sets are recursively enumerable. The complement of every recursively enumerable sets is recursively enumerable. Every Non-empty recursively enumerable set is the range of some totally recursive function. All finite sets are recursive. The complement of every recursive set is recursive.
Which of the following statement is FALSE?All recursive sets are recursively enumerable.The complement of every recursively enumerable sets is recursively enumerable.Ever...
makhdoom ghaya
2.5k
views
makhdoom ghaya
asked
Oct 11, 2015
Theory of Computation
tifr2010
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
5
votes
1
answer
232
Which of the following is not a recursive Language? Please explain the reason for each
Which of the following is not a recursive language? a. Regular language b. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$} c. {$\langle M \rangle$ | $M$ is a TM and there exists an input which halts within $100$ steps} d. {$\langle M \rangle$ | $M$ is a TM and $L(M)$ is regular }
Which of the following is not a recursive language?a. Regular languageb. {$\langle M,w \rangle$ | $M$ is a DFA that accepts $w$}c. {$\langle M \rangle$ | $M$ is a TM and ...
Shefali
1.3k
views
Shefali
asked
Sep 11, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
+
–
6
votes
4
answers
233
Let A and B be disjoint, R.E. languages. Let A' U B' also be recursive enumerable. What can you say about A and B?
Let $A$ and $B$ be disjoint, R.E. languages. Let $\bar A \cup \bar B$ also be recursive enumerable. What can you say about $A$ and $B$?(a) Neither A nor B is decidable is...
ari
3.1k
views
ari
asked
Aug 18, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
3
votes
1
answer
234
is the set of recursively enumerable languages countable?
Shubham Sahu
4.3k
views
Shubham Sahu
asked
Jul 15, 2015
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
30
votes
2
answers
235
GATE CSE 2015 Set 1 | Question: 3
For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true? $\bar{L}_{1}$ ( Complement of $L_{1}$) is recursive $\bar{L}_{2}$ ... $\bar{L}_{1}$ ∪ $L_{2}$ is recursively enumerable I only III only III and IV only I and IV only
For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessa...
makhdoom ghaya
6.5k
views
makhdoom ghaya
asked
Feb 11, 2015
Theory of Computation
gatecse-2015-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
normal
+
–
24
votes
1
answer
236
Which of the following languages are Recursively Enumerable language?
Which of the following languages are Recursively Enumerable language? $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ ... $\{ \langle M1, M2, M3 \rangle \mid L(M1) = L(M2) \cup L(M3) \}$ All of these
Which of the following languages are Recursively Enumerable language?$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which...
Vikrant Singh
5.2k
views
Vikrant Singh
asked
Jan 27, 2015
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
theory-of-computation
+
–
7
votes
2
answers
237
Given Language is REC or Non RE
Which of the following is true for the given language? $L=$ {<TM> | TM halts on every input} <TM> is encoding of the Turing machine (A) $L$ is Recursive and $\overline{L}$ is also Recursive (B) $L$ is Recursive ... Enumerable and $\overline{L}$ is Recursive Enumerable (D) $L$ is Non Recursive Enumerable and $\overline{L}$ is Non Recursive Enumerable
Which of the following is true for the given language?$L=$ {<TM | TM halts on every input}<TM is encoding of the Turing machine(A) $L$ is Recursive and $\overline{L}$ is ...
Manu Thakur
3.1k
views
Manu Thakur
asked
Nov 15, 2014
Theory of Computation
theory-of-computation
difficult
recursive-and-recursively-enumerable-languages
decidability
+
–
58
votes
2
answers
238
GATE CSE 2010 | Question: 17
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true? $L_2 - L_1 \:\text{is recursively enumerable.}$ ... $L_2 \cap L_3 \:\text{is recursively enumerable.}$ $L_2 \cup L_3 \:\text{is recursively enumerable.}$
Let $L_1$ be the recursive language. Let $L_2$ and $L_3$ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessar...
go_editor
16.2k
views
go_editor
asked
Sep 29, 2014
Theory of Computation
gatecse-2010
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
normal
+
–
59
votes
4
answers
239
GATE CSE 2014 Set 2 | Question: 16
Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE? If $A\: \leq_m B$ and $B$ is recursive then $A$ ... then $A$ is recursively enumerable. If $A\: \leq_m B$ and $B$ is not recursively enumerable then $A$ is not recursively enumerable.
Let $A\:\leq_m\:B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$. Which one of the following is FALSE?If $A\: \leq_...
go_editor
17.5k
views
go_editor
asked
Sep 28, 2014
Theory of Computation
gatecse-2014-set2
theory-of-computation
recursive-and-recursively-enumerable-languages
normal
+
–
35
votes
3
answers
240
GATE CSE 2014 Set 1 | Question: 35
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)$. One of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e. Both $L$ and $\bar{L}$ are r.e. but not recursive. Both $L$ and $\bar{L}$ are recursive.
Let $L$ be a language and $\bar{L}$ be its complement. Which one of the following is NOT a viable possibility?Neither $L$ nor $\bar{L}$ is recursively enumerable $(r.e.)...
go_editor
8.4k
views
go_editor
asked
Sep 26, 2014
Theory of Computation
gatecse-2014-set1
theory-of-computation
easy
recursive-and-recursively-enumerable-languages
+
–
Page:
« prev
1
...
3
4
5
6
7
8
9
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register