search
Log In

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?
asked Dec 20, 2018 in Theory of Computation subho16 90 views
0 votes
0 answers
2
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?
asked Dec 17, 2018 in Theory of Computation Harsh Kumar 62 views
0 votes
2 answers
4
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 harsh yadav 184 views
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.
asked Nov 23, 2018 in Theory of Computation Mk Utkarsh 121 views
0 votes
1 answer
7
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?
asked Nov 14, 2018 in Theory of Computation Mizuki 137 views
0 votes
1 answer
11
0 votes
1 answer
12
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?
asked Nov 5, 2018 in Theory of Computation Abhisek Tiwari 4 57 views
0 votes
1 answer
15
0 votes
0 answers
16
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
asked Oct 16, 2018 in Theory of Computation Smishra95 118 views
0 votes
2 answers
18
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?
asked Oct 8, 2018 in Theory of Computation Somoshree Datta 5 417 views
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
asked Sep 11, 2018 in Theory of Computation goluabhinan 84 views
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
asked Sep 9, 2018 in Theory of Computation Na462 54 views
0 votes
1 answer
24
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
asked Aug 10, 2018 in Theory of Computation manisha11 212 views
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?
asked Apr 4, 2018 in Theory of Computation Na462 92 views
0 votes
0 answers
29
1 vote
1 answer
30
...