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