Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged recursive-and-recursively-enumerable-languages
1
votes
2
answers
121
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps.Please elaborate.
Mizuki
496
views
Mizuki
asked
Nov 14, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
1
answer
122
Gate 2016 - 2 - 8
In the first one, why is L3 compliment recursively enumerable? https://gateoverflow.in/39574#39584
In the first one, why is L3 compliment recursively enumerable?https://gateoverflow.in/39574#39584
Mizuki
207
views
Mizuki
asked
Nov 12, 2018
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
1
votes
0
answers
123
MadeEasy Test Series: Theory Of Computation - Recursive and Recursively Enumerable Languages
Why L1 is not recursive?
Why L1 is not recursive?
Vikas Verma
352
views
Vikas Verma
asked
Nov 8, 2018
Theory of Computation
made-easy-test-series
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
124
Recursive language
https://gateoverflow.in/86546/theory-of-computation-22 Total recursive functions are similar to a) Recursive Languages b) Recursive Enumerable languages c) can not relate d) none what is partial,preemptive and total recursive function and how related to Mentioned languages???? "Recursive Enumerable language is range of total recursive function"What it means?
https://gateoverflow.in/86546/theory-of-computation-22Total recursive functions are similar to a) Recursive Languages b) Recursive Enumerable languages c) can not re...
Abhisek Tiwari 4
318
views
Abhisek Tiwari 4
asked
Nov 5, 2018
Theory of Computation
recursive-and-recursively-enumerable-languages
turing-machine
theory-of-computation
+
–
0
votes
1
answer
125
Turing machine
What is the meaning of non trivial property related to a language. Please explain with an example.
What is the meaning of non trivial property related to a language. Please explain with an example.
Lovejeet Singh
209
views
Lovejeet Singh
asked
Oct 30, 2018
Theory of Computation
turing-machine
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
126
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
aditi19
247
views
aditi19
asked
Oct 29, 2018
Theory of Computation
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
5
votes
1
answer
127
DECIDABILITY
L = {<M> | L(M) = {1}} L = {<M> | L(M) is {} } L = {<M> | L(M) has exactly 100 strings} which are REC R E BUT not REC , NOT EVEN RE
L = {<M | L(M) = {1}}L = {<M | L(M) is {} }L = {<M | L(M) has exactly 100 strings} which are REC R E BUT not REC , NOT EVEN RE
Smishra95
597
views
Smishra95
asked
Oct 16, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
theory-of-computation
+
–
0
votes
2
answers
128
GateForum Test Series: Theory Of Computation - Recursive and Recursively Enumerable Languages
What is Turing Decidable and Turing Recognizable and What to conclude from those terms?
What is Turing Decidable and Turing Recognizable and What to conclude from those terms?
Gupta731
625
views
Gupta731
asked
Oct 10, 2018
Theory of Computation
gateforum-test-series
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
1
votes
0
answers
129
GateForum Test Series: Theory Of Computation - Recursive and Recursively Enumerable Languages
Gupta731
294
views
Gupta731
asked
Oct 10, 2018
Theory of Computation
gateforum-test-series
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
3
votes
2
answers
130
Decidability
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$ Is $L_1$ RE or not RE?
$L_1= \{\langle M\rangle \mid $ there exists $x \in \Sigma^*$ such that for every $y \in L(M), xy \notin L(M)\}.$Is $L_1$ RE or not RE?
Somoshree Datta 5
2.0k
views
Somoshree Datta 5
asked
Oct 8, 2018
Theory of Computation
recursive-and-recursively-enumerable-languages
decidability
+
–
0
votes
0
answers
131
MadeEasy Test Series: Theory Of Computation - Recursive and RE Languages
how can l2 be a recursive language we have two turing machines both can accept one language but it does not imply whether it halts or not
how can l2 be a recursive language we have two turing machines both can accept one language but it does not imply whether it halts or not
garimanand
167
views
garimanand
asked
Sep 18, 2018
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
made-easy-test-series
+
–
0
votes
1
answer
132
Doubt in Turing Machines
Consider the following T.M. {Note Σ ={a,b} ⌈ = {*,a,b} Δ = empty cells of Tape. Which of the following string does not accepted by T.M. ? (i) aabbaa (ii) ε (iii) aabb
Consider the following T.M.{Note Σ ={a,b}⌈ = {*,a,b}Δ = empty cells of Tape.Which of the following string does not accepted by T.M. ?(i) aabbaa(ii) ε(iii) aabb
goluabhinan
839
views
goluabhinan
asked
Sep 11, 2018
Theory of Computation
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
133
Turing machine
Consider <M> be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M> | M is a TM that halts on all the input and L(M) = L' for some Undecidable language L' } then L is ? A. Decidable and Recursive B. Decidable and Non recursive C. Undecidable and RE D. Undecidable and Non RE
Consider <M be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M | M is a TM that halts on all the input and L(M) = L' for some Undecidable langu...
Na462
249
views
Na462
asked
Sep 9, 2018
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
decidability
+
–
0
votes
1
answer
134
Decidability Doubt
Can someone explain in simple words 'Membership problem is undecidable"?
Can someone explain in simple words 'Membership problem is undecidable"?
aditi19
1.2k
views
aditi19
asked
Sep 8, 2018
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
135
Decidability
Ans. B
Ans. B
Na462
389
views
Na462
asked
Sep 2, 2018
Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
2
votes
2
answers
136
TOC decidability
Let <M> be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M> | M is TM on input w will visit some state P}. The language L is (a) Decidable (b) Undecidable but partially decidable (c) Undecidable and not even partially decidable (d) Not a decision problem
Let <M be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M | M is TM on input w will visit some state P}.The language L is(a) Decidable(b) Undecid...
manisha11
744
views
manisha11
asked
Aug 10, 2018
Theory of Computation
decidability
recursive-and-recursively-enumerable-languages
turing-machine
+
–
0
votes
0
answers
137
Compiler Design from University papers
Ronish Jariwala 1
209
views
Ronish Jariwala 1
asked
Apr 15, 2018
Compiler Design
compiler-design
recursive-and-recursively-enumerable-languages
compilation-phases
+
–
1
votes
0
answers
138
Turing Machine
$L(M)$ = Contains atmost $10$ Strings ? Is it Recursively enumerable ? According to me its Not. Because according to Rices theorem there exist a non monotonic property which makes it Non recognizable. because $T_{yes}$ = $\phi$(i.e. NULL) and $T_{no} = (a+b)^* $ say $\Sigma = \{a,b\} $ and $T_{yes}$ is proper subset of $T_{no}$ Hence its not Recursively enumerable right?
$L(M)$ = Contains atmost $10$ Strings ? Is it Recursively enumerable ?According to me its Not. Because according to Rices theorem there exist a non monotoni...
Na462
333
views
Na462
asked
Apr 4, 2018
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
139
Type of Language
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
Chhotu
291
views
Chhotu
asked
Jan 31, 2018
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
2
votes
2
answers
140
decidable problem
Let L be a DCFL and R is a regular language. Consider the below given problems. P: Is L=R ? Q: Is R ⊆L ? Discuss decidablity of P and Q.
Let L be a DCFL and R is a regular language. Consider the below given problems.P: Is L=R ?Q: Is R ⊆L ?Discuss decidablity of P and Q.
MIRIYALA JEEVAN KUMA
1.2k
views
MIRIYALA JEEVAN KUMA
asked
Jan 21, 2018
Theory of Computation
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
+
–
6
votes
4
answers
141
Intersection of two Recursive languages are of same type or not. Is it decidable or undecidable?
Since Recursive languages are closed under intersection, therefore it decidable. Am I wrong?
Since Recursive languages are closed under intersection, therefore it decidable. Am I wrong?
nikhil_cs
2.9k
views
nikhil_cs
asked
Jan 18, 2018
Theory of Computation
recursive-and-recursively-enumerable-languages
decidability
+
–
3
votes
0
answers
142
made easy test series
A) Decidable REC B) Undecidable and RE C) Undecidable and non RE D) Decidable but RE
A) Decidable RECB) Undecidable and REC) Undecidable and non RED) Decidable but RE
yankur9
339
views
yankur9
asked
Jan 13, 2018
Theory of Computation
turing-machine
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
143
Turing machine
If L is accepted by TM, which halts on every string over alphabet {a, b}, then L′ is recursive language. True or False ? I think false because L′ = TM halts on no string in {a,b} = $\phi$ and L(TM) = $\phi$ is non RE, let alone it being recursive
If L is accepted by TM, which halts on every string over alphabet {a, b}, then L′ is recursive language.True or False ?I think false because L′ = TM halts on no strin...
just_bhavana
774
views
just_bhavana
asked
Jan 1, 2018
Theory of Computation
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
2
votes
4
answers
144
Decidability
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ is a) Decidable b) Semi decidable c) not even semi-decidable
The problem described by the language $L = \left\{ \langle M_1,M_2 \rangle \mid L(M_1) = L(M_2) \right\}$ isa) Decidable b) Semi decidable c) not even semi-decidable
Abhishek Kumar Singh
1.1k
views
Abhishek Kumar Singh
asked
Dec 30, 2017
Theory of Computation
decidability
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
145
Turing Machine
A. L is undecidable B. L is decidable C. L is regular. D. None of these. Please explain in detail.
A. L is undecidableB. L is decidableC. L is regular.D. None of these.Please explain in detail.
Shubham Kumar Gupta
563
views
Shubham Kumar Gupta
asked
Dec 23, 2017
Theory of Computation
turing-machine
theory-of-computation
decidability
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
146
Previous year gate question Toc
Define languages L0L0 and L1L1 as follows : L0={⟨M,w,0⟩∣M halts on w}L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halts on w}L1={⟨M,w,1⟩∣M does not halts on w} Here ⟨M,w,i⟩⟨M,w,i⟩ is a triplet, whose first ... @others As L0 is recursive as it halt And L1 is recursive enumerable as it does not halt So recursive U recursive enumerable will recursive enumerable rt?
Define languages L0L0 and L1L1 as follows : L0={⟨M,w,0⟩∣M halts on w}L0={⟨M,w,0⟩∣M halts on w} L1={⟨M,w,1⟩∣M does not halts on w}L1={⟨M,w,1⟩∣M doe...
hem chandra joshi
1.3k
views
hem chandra joshi
asked
Dec 1, 2017
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
0
answers
147
What is meant by enumeration in context of language?
What is meant by enumeration in context of language?What are not recursively enumerable language?
What is meant by enumeration in context of language?What are not recursively enumerable language?
hem chandra joshi
428
views
hem chandra joshi
asked
Dec 1, 2017
Theory of Computation
recursive-and-recursively-enumerable-languages
+
–
2
votes
1
answer
148
Turing Machine
L1={<M>| M is a Turing Machine , P is a TM that halts on all input, and P$\epsilon$L(M)} L2={<M>| M is a Turing Machine , P is a TM that halts on all input, and M$\epsilon$L(P)} Which one REC, or RE or non RE ?
L1={<M>| M is a Turing Machine , P is a TM that halts on all input, and P$\epsilon$L(M)}L2={<M>| M is a Turing Machine , P is a TM that halts on all input, and M$\epsilon...
srestha
1.0k
views
srestha
asked
Nov 29, 2017
Theory of Computation
turing-machine
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
0
votes
2
answers
149
Turing machine and Recursive Language
If total turing machine is a proper subset of turing machine then why recursive language is not a proper subset of Recursive Enumerable ?
If total turing machine is a proper subset of turing machine then why recursive language is not a proper subset of Recursive Enumerable ?
Mk Utkarsh
2.0k
views
Mk Utkarsh
asked
Nov 26, 2017
Theory of Computation
turing-machine
theory-of-computation
recursive-and-recursively-enumerable-languages
+
–
1
votes
1
answer
150
#TOC Turing Machine Question
For every deterministic Turing machine, there exists an equivalent deterministic Non Deterministic Turing machine. I know, other way is correct i.e for every DTM there exist a NDTM, but is above TRUE/FALSE. Thank you!
For every deterministic Turing machine, there exists an equivalent deterministic Non Deterministic Turing machine.I know, other way is correct i.e for every DTM there exi...
iarnav
892
views
iarnav
asked
Nov 1, 2017
Theory of Computation
turing-machine
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
self-doubt
+
–
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