Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged recursive-and-recursively-enumerable-languages
0
votes
0
answers
91
Peter Linz Edition 5 Exercise 11.1 Question 9 (Page No. 284)
Show that the families of recursively enumerable and recursive languages are closed under reversal.
Show that the families of recursively enumerable and recursive languages are closed under reversal.
Rishi yadav
193
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
92
Peter Linz Edition 5 Exercise 11.1 Question 8 (Page No. 284)
Show that the family of recursive languages is closed under union and intersection.
Show that the family of recursive languages is closed under union and intersection.
Rishi yadav
149
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
93
Peter Linz Edition 5 Exercise 11.1 Question 7 (Page No. 284)
Is the family of recursively enumerable languages closed under intersection$?$
Is the family of recursively enumerable languages closed under intersection$?$
Rishi yadav
211
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
94
Peter Linz Edition 5 Exercise 11.1 Question 6 (Page No. 284)
Show that the family of recursively enumerable languages is closed under union.
Show that the family of recursively enumerable languages is closed under union.
Rishi yadav
107
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
95
Peter Linz Edition 5 Exercise 11.1 Question 5 (Page No. 284)
Show that if a language is not recursively enumerable, its complement cannot be recursive.
Show that if a language is not recursively enumerable, its complement cannot be recursive.
Rishi yadav
117
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
96
Peter Linz Edition 5 Exercise 11.1 Question 4 (Page No. 284)
Let $L$ be a context-free language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for it.
Let $L$ be a context-free language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for it.
Rishi yadav
131
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
97
Peter Linz Edition 5 Exercise 11.1 Question 3 (Page No. 284)
Let $L$ be a finite language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for $L^+$
Let $L$ be a finite language. Show that then $L^+$ is recusively enumerable. Suggest an enumeration procedure for $L^+$
Rishi yadav
257
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
98
Peter Linz Edition 5 Exercise 11.1 Question 2 (Page No. 284)
Prove that the set of all languages that are not recursively enumerable is not countable.
Prove that the set of all languages that are not recursively enumerable is not countable.
Rishi yadav
172
views
Rishi yadav
asked
Mar 16, 2019
Theory of Computation
peter-linz
peter-linz-edition5
theory-of-computation
proof
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
99
ACE Full Length Mock Test-8
Let L be recursively enumerable languages. There is an algorithm that can enumerate all string of L in proper order. If language M is reducible to L then which of the following is correct ? M is REL but not recursive Complement of M is not REL M $\cap$ L is recursive None of these
Let L be recursively enumerable languages. There is an algorithm that can enumerate all string of L in proper order. If language M is reducible to L then which of the fol...
register_user_19
261
views
register_user_19
asked
Jan 25, 2019
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
100
Ace Test Series: Theory Of Computation - Decidablity
Shankar Kakde
400
views
Shankar Kakde
asked
Jan 23, 2019
Theory of Computation
recursive-and-recursively-enumerable-languages
theory-of-computation
ace-test-series
decidability
+
–
0
votes
0
answers
101
ACE Test series on Recursively Enumerable Language
Shankar Kakde
188
views
Shankar Kakde
asked
Jan 14, 2019
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
102
MadeEasy Test Series: Theory of Computation - Recursive and RE Languages
Which of the following languages are recursive? L1: { <M,k> | M is a turing machine and |{ w ∈ L(M) : w ∈ a*b* } | <=k} L2: { <M> | there exists a turing machine M’ such that <M> ≠ <M’> and L(M) = L(M’)
Which of the following languages are recursive?L1: { <M,k | M is a turing machine and |{ w ∈ L(M) : w ∈ a*b* } | <=k}L2: { <M | there exists a turing machine M’ suc...
Sambhrant Maurya
245
views
Sambhrant Maurya
asked
Jan 9, 2019
Theory of Computation
made-easy-test-series
turing-machine
recursive-and-recursively-enumerable-languages
+
–
2
votes
0
answers
103
RE or non RE
CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty} Which of the following is true? a- Decidable REC B- Undecidable and RE c-Undecidable and non RE d- Decidable but RE
CONSIDER THE FLLOWING LANGUAGE L={<M>| M is a TM and L(M)=empty}Which of the following is true?a- Decidable RECB- Undecidable and REc-Undecidable and non REd- Decidable ...
bts1jimin
611
views
bts1jimin
asked
Jan 8, 2019
Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
104
Language accepted by this Turing Machine
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.
sripo
538
views
sripo
asked
Jan 5, 2019
Theory of Computation
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
regular-expression
+
–
1
votes
1
answer
105
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.
Ayan21
507
views
Ayan21
asked
Dec 30, 2018
Theory of Computation
decidability
theory-of-computation
context-free-language
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
106
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.
Deepanshu
944
views
Deepanshu
asked
Dec 29, 2018
Theory of Computation
rice-theorem
recursive-and-recursively-enumerable-languages
+
–
4
votes
1
answer
107
GATE Overflow | Mock GATE | Test 1 | Question: 56
Consider the following language $L$: $L=\{<M,x,k> \mid M \text{ is a Turing Machine and M does not halt on x within k steps} \}$ The language family to which $L$ belongs is not closed under? Intersection Homomorphism Set Difference Complementation
Consider the following language $L$:$L=\{<M,x,k \mid M \text{ is a Turing Machine and M does not halt on x within k steps} \}$The language family to which $L$ belongs is ...
Ruturaj Mohanty
1.7k
views
Ruturaj Mohanty
asked
Dec 27, 2018
Theory of Computation
go-mockgate-1
recursive-and-recursively-enumerable-languages
theory-of-computation
turing-machine
closure-property
+
–
0
votes
1
answer
108
MadeEasy Test Series: Theory Of Computation - Recursive And Recursive Enumerable Languages
consider the following problems p1: {<M,x,k>| M is a Turing machine M does not halt on x within k steps } p2:{<M>|M is a Turing machine and M accepts at least two strings of different length ... exists an input whose length is less than 100 on which M halts } the problems which are RE but not REC?
consider the following problemsp1: {<M,x,k>| M is a Turing machine M does not halt on x within k steps }p2:{<M>|M is a Turing machine and M accepts at least two strings o...
suneetha
1.3k
views
suneetha
asked
Dec 24, 2018
Theory of Computation
made-easy-test-series
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
109
decidability
please someone explain what are these problems and how to solve these problems for every language with proper explanation? MEMBERSHIP PROBLEM EMPTINESS PROBLEM COMPLETENESS PROBLEM EQUILITY PROBLEM SUBSET PROBLEM DISJOINTNESS PROBLEM IS GIVEN LANGUAGE REGULAR FINITENESS PROBLEM
please someone explain what are these problems and how to solve these problems for every language with proper explanation?MEMBERSHIP PROBLEMEMPTINESS PROBLEMCOMPLETENESS ...
Rahul_Rathod_
958
views
Rahul_Rathod_
asked
Dec 24, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
110
Self doubt
I know that for a recursively enumerable language there exists an unrestricted grammar and we have formally defined unrestricted grammar. I want to know whether for every recursive language, there is a grammar or not, and if there is, is there a formal definition of the same?
I know that for a recursively enumerable language there exists an unrestricted grammar and we have formally defined unrestricted grammar. I want to know whether for every...
subho16
518
views
subho16
asked
Dec 20, 2018
Theory of Computation
theory-of-computation
turing-machine
grammar
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
111
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.
Ayan21
604
views
Ayan21
asked
Dec 17, 2018
Theory of Computation
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
0
votes
1
answer
112
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...
Harsh Kumar
310
views
Harsh Kumar
asked
Dec 17, 2018
Theory of Computation
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
2
answers
113
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.
harsh yadav
966
views
harsh yadav
asked
Dec 14, 2018
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
1
votes
3
answers
114
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)
gmrishikumar
1.7k
views
gmrishikumar
asked
Dec 10, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
theory-of-computation
turing-machine
rice-theorem
+
–
0
votes
3
answers
115
NIELIT 2018-81
Identify the true statement from the given statements: A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language. The complement of a recursive languages is recursive The complement of a context-free language is context-free Only $1$ $1$ and $2$ $1$, $2$ and $3$ $2$ and $3$
Identify the true statement from the given statements:A recursive formal language is a recursive subset in the set of all possible words over the alphabet of the language...
Arjun
1.4k
views
Arjun
asked
Dec 7, 2018
Theory of Computation
nielit-2018
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
116
Decidability Doubt
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$ ... because $\exists$ infinite number of TM's which accept $\Sigma^*$. Now $L(M)$ is not even RE. If that then how $L_1$ is RE. Please explain both.
$L_1 = \{ \text{<M>} | \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$$L_2 = \{ \text{<M>} | \ \text{M is a TM,...
Mk Utkarsh
418
views
Mk Utkarsh
asked
Nov 23, 2018
Theory of Computation
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
0
votes
1
answer
117
General Topic Doubt Theory of Computation: Recursive And Recursively Enumerable Languages
State True or False with a reason .Is Recursive lang. turing recognizable
State True or False with a reason .Is Recursive lang. turing recognizable
Pavan Shetty
828
views
Pavan Shetty
asked
Nov 17, 2018
Theory of Computation
recursive
recursive-and-recursively-enumerable-languages
general-topic-doubt
+
–
1
votes
0
answers
118
Decidability
Na462
1.6k
views
Na462
asked
Nov 14, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
119
Decidability
Na462
416
views
Na462
asked
Nov 14, 2018
Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
120
Decidability
How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category it falls?
How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category...
Mizuki
467
views
Mizuki
asked
Nov 14, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
Page:
« prev
1
2
3
4
5
6
7
8
9
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
