The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
1
recursive language
Can a language exist which is undecidable as well as Recursive language ? If yes please give example.
asked
Dec 15, 2018
in
Theory of Computation
by
harsh yadav
(
127
points)

125
views
recursiveandrecursivelyenumerablelanguages
0
votes
2
answers
2
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
asked
Dec 10, 2018
in
Theory of Computation
by
gmrishikumar
Active
(
2.1k
points)

185
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
turingmachine
ricetheorem
0
votes
0
answers
3
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) \}$ ... infinite 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.
asked
Nov 23, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
35.7k
points)

94
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
4
General Topic Doubt Theory of Computation: Recursive And Recursively Enumerable Languages
asked
Nov 17, 2018
in
Theory of Computation
by
Pavan Shetty
(
77
points)

95
views
recursive
recursiveandrecursivelyenumerablelanguages
generaltopicdoubt
0
votes
0
answers
5
Decidability
asked
Nov 14, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

277
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
6
Decidability
asked
Nov 14, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

63
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
7
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?
asked
Nov 14, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

76
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
8
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
asked
Nov 14, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

89
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
9
Gate 2016  2  8
In the first one, why is L3 compliment recursively enumerable? https://gateoverflow.in/39574#39584
asked
Nov 12, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

42
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
10
MadeEasy Test Series: Theory Of Computation  Recursive and Recursively Enumerable Languages
asked
Nov 8, 2018
in
Theory of Computation
by
Vikas Verma
Active
(
3.3k
points)

75
views
madeeasytestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
11
Recursive language
https://gateoverflow.in/86546/theoryofcomputation22 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?
asked
Nov 5, 2018
in
Theory of Computation
by
Abhisek Tiwari 4
Active
(
5.2k
points)

44
views
recursiveandrecursivelyenumerablelanguages
turingmachine
theoryofcomputation
0
votes
1
answer
12
Turing machine
What is the meaning of non trivial property related to a language. Please explain with an example.
asked
Oct 30, 2018
in
Theory of Computation
by
Lovejeet Singh
(
39
points)

37
views
turingmachine
theory
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
13
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
asked
Oct 29, 2018
in
Theory of Computation
by
aditi19
Active
(
5.1k
points)

81
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
+4
votes
1
answer
14
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
asked
Oct 16, 2018
in
Theory of Computation
by
Smishra95
Active
(
1.4k
points)

94
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
0
votes
2
answers
15
GateForum Test Series: Theory Of Computation  Recursive and Recursively Enumerable Languages
asked
Oct 10, 2018
in
Theory of Computation
by
Gupta731
Active
(
4.7k
points)

78
views
gateforumtestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
16
GateForum Test Series: Theory Of Computation  Recursive and Recursively Enumerable Languages
asked
Oct 10, 2018
in
Theory of Computation
by
Gupta731
Active
(
4.7k
points)

61
views
gateforumtestseries
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
2
answers
17
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?
asked
Oct 8, 2018
in
Theory of Computation
by
Somoshree Datta 5
Active
(
5k
points)

297
views
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
0
answers
18
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
asked
Sep 18, 2018
in
Theory of Computation
by
garimanand
Active
(
1.6k
points)

23
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
madeeasytestseries
0
votes
1
answer
19
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
asked
Sep 11, 2018
in
Theory of Computation
by
goluabhinan
(
71
points)

45
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
20
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
asked
Sep 9, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

40
views
turingmachine
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
1
answer
21
Decidability Doubt
Can someone explain in simple words 'Membership problem is undecidable"?
asked
Sep 8, 2018
in
Theory of Computation
by
aditi19
Active
(
5.1k
points)

43
views
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
22
Decidability
Ans. B
asked
Sep 2, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

53
views
decidability
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
23
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
asked
Aug 10, 2018
in
Theory of Computation
by
manisha11
Active
(
2.3k
points)

113
views
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
0
answers
24
Compiler Design from University papers
asked
Apr 16, 2018
in
Compiler Design
by
Ronish Jariwala 1
(
71
points)

55
views
compilerdesign
recursiveandrecursivelyenumerablelanguages
compilationphases
+1
vote
0
answers
25
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?
asked
Apr 4, 2018
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

82
views
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
26
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 ?
asked
Jan 31, 2018
in
Theory of Computation
by
Chhotu
Boss
(
13.3k
points)

45
views
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
27
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.
asked
Jan 21, 2018
in
Theory of Computation
by
MIRIYALA JEEVAN KUMA
Active
(
2.4k
points)

204
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
+3
votes
2
answers
28
Intersection of two Recursive languages are of same type or not. Is it decidable or undecidable?
asked
Jan 18, 2018
in
Theory of Computation
by
nikhil_cs
Junior
(
675
points)

422
views
recursiveandrecursivelyenumerablelanguages
decidability
+3
votes
0
answers
29
made easy test series
A) Decidable REC B) Undecidable and RE C) Undecidable and non RE D) Decidable but RE
asked
Jan 13, 2018
in
Theory of Computation
by
yankur9
Active
(
2k
points)

67
views
turingmachine
recursiveandrecursivelyenumerablelanguages
+1
vote
1
answer
30
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
asked
Jan 1, 2018
in
Theory of Computation
by
just_bhavana
Boss
(
12.1k
points)

166
views
recursiveandrecursivelyenumerablelanguages
Page:
« prev
1
2
3
4
5
6
7
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged recursiveandrecursivelyenumerablelanguages
Recent Blog Comments
Lakshman Patel RJIT Do you have such notes...
Great work sir
Yes Sir, It will be very helpful if we get...
@arjun sir is there a pdf...
Really helpful sir Thanks a ton👍👍
50,645
questions
56,563
answers
195,735
comments
101,658
users