# Recent questions tagged recursive-and-recursively-enumerable-languages

0 votes
0 answers
1
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?
0 votes
0 answers
2
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.
0 votes
1 answer
3
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?
0 votes
2 answers
4
Can a language exist which is undecidable as well as Recursive language ? If yes please give example.
0 votes
2 answers
5
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
0 votes
0 answers
6
$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) \}$ ... language is 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.
0 votes
1 answer
7
State True or False with a reason .Is Recursive lang. turing recognizable
1 vote
0 answers
8
0 votes
1 answer
9
0 votes
1 answer
10
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?
0 votes
1 answer
11
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
0 votes
1 answer
12
In the first one, why is L3 compliment recursively enumerable? https://gateoverflow.in/39574#39584
0 votes
0 answers
13
Why L1 is not recursive?
0 votes
0 answers
14
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?
0 votes
1 answer
15
What is the meaning of non trivial property related to a language. Please explain with an example.
0 votes
0 answers
16
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
4 votes
1 answer
17
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
0 votes
2 answers
18
What is Turing Decidable and Turing Recognizable and What to conclude from those terms?
1 vote
0 answers
19
1 vote
2 answers
20
$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?
0 votes
0 answers
21
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
0 votes
1 answer
22
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
0 votes
0 answers
23
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
0 votes
1 answer
24
Can someone explain in simple words 'Membership problem is undecidable"?
0 votes
0 answers
25
Ans. B
1 vote
1 answer
26
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
0 votes
0 answers
27
1 vote
0 answers
28
$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?
0 votes
0 answers
29
Hi Guys, What is the type of $L_{1}$ and $L_{2}$ ? If they are REC then How could it be proved ?
1 vote
1 answer
30
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.