Dark Mode

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

0 votes

0 answers

1

Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non- ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?

dopq12 asked in Theory of Computation Mar 5

by dopq12

75 views

5 votes

1 answer

2

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55
Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$. Which of the following sets is not ... machine halts on the input $m$. The set of $n$ such that all Turing machines halt on the input $n$.

GO Classes asked in Theory of Computation Jan 28

470 views

0 votes

0 answers

3

ISRO 2024
which of the following statements is NOT true? If a language is recursive it complement is recursive If a language is recursive its complement is recursively enumerable If a language and its complement are recursively enumerable it is recursive If a language is recursively enumerable its complement is also recursively enumerable

Ramayya asked in Theory of Computation Jan 7

139 views

1 vote

0 answers

4

Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language

amitarp818 asked in Theory of Computation Dec 28, 2023

234 views

0 votes

1 answer

5

Self Doubt
Consider L is recursive language and G is Recursively Enumerable then, L' union G is Recursively enumerable. Can someone please explain me this statement why it is true.?

TusharKumar asked in Theory of Computation Jan 21, 2023

315 views

0 votes

1 answer

6

Unacademy Test
Consider the following language: L = {<M>|M halts after 200 steps for all inputs} Which of the following is True about L? A.L is decidable B.L is undecidable C.Cannot be predicted D.None of the above

Rajender gill asked in Theory of Computation Dec 21, 2022

by Rajender gill

528 views

0 votes

0 answers

7

Unacademy Test
Consider the following language: L = {< M > | L(M) has atleast 10 strings} Which of the following is true about L? A.L is decidable B.L is Turing recognizable C.L is not recursive D.None of these

Rajender gill asked in Theory of Computation Dec 21, 2022

by Rajender gill

500 views

3 votes

2 answers

8

Is it also CSL?
Is the following Language, L = {xxxx | x ∈ {0, 1}*} CSL or not? I saw a explanation say that it’s REC, but it didn’t say anything about it not being CSL and I used to think strings like {xx | x ∈ {0, 1}*} are CSL where the same strings keep repeating [like x here]. So is it CSL and please do also tell is there a rule to figure that out?

h4kr asked in Theory of Computation Dec 18, 2022

by h4kr

767 views

1 vote

1 answer

9

NIELIT 2022 April Scientist B | Section B | Question: 43
Consider the following types of languages: $\text{L1}:$ Regular, $\text{L2}:$ Context-free, $\text{L3}:$ Recursive, $\text{L4}:$ Recursively enumerable. Which of the following is/are $\text{TRUE}$ ? $\text{L3}' \cup \text{L4}$ is recursively ... and $\text{III}$ only $\text{I}$ and $\text{IV}$ only $\text{I, II}$ and $\text{III}$ only

soujanyareddy13 asked in Theory of Computation Apr 12, 2022

by soujanyareddy13

2.8k views

6 votes

2 answers

10

GATE CSE 2022 | Question: 13
Which of the following statements is/are $\text{TRUE}?$ Every subset of a recursively enumerable language is recursive. If a language $\textit{L}$ and its complement $\overline{\textit{L}}$ are both recursively enumerable, then $\textit{L}$ must be recursive. ... $\textit{L}_{1} \cap \textit{L}_{2}$ must be deterministic context-free.

Arjun asked in Theory of Computation Feb 15, 2022

by Arjun

14.9k views

17 votes

3 answers

11

GATE CSE 2021 Set 1 | Question: 12
Let $\langle M \rangle$ denote an encoding of an automaton $M$. Suppose that $\Sigma = \{0,1\}$. Which of the following languages is/are $\text{NOT}$ recursive? $L= \{ \langle M \rangle \mid M$ is a $\text{DFA}$ such that $L(M)=\emptyset \}$ ... that $L(M)=\emptyset \}$ $L= \{ \langle M \rangle \mid M$ is a $\text{PDA}$ such that $L(M)=\Sigma ^* \}$

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

7.2k views

14 votes

5 answers

12

GATE CSE 2021 Set 1 | Question: 39
For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$ ... decidable $L_1$ is decidable and $L_2$ is undecidable $L_1$ is undecidable and $L_2$ is decidable Both $L_1$ and $L_2$ are undecidable

Arjun asked in Theory of Computation Feb 18, 2021

by Arjun

9.8k views

2 votes

2 answers

13

UGC NET CSE | October 2020 | Part 2 | Question: 27
Consider $L=L_1 \cap L_2$ where $L_1 = \{ 0^m 1^m 20^n 1^n \mid m,n \geq 0 \}$ $L_2 = \{0^m1^n2^k \mid m,n,k \geq 0 \}$ Then, the language $L$ is Recursively enumerable but not context free Regular Context free but not regular Not recursive

go_editor asked in Theory of Computation Nov 20, 2020

2.2k views

0 votes

1 answer

14

NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 9
A language $L$ for which there exists a $TM\;\;’T’,$ that accepts every word in $L$ and either rejects or loops for every word that is not in $L,$ is said to be Recursive Recursively enumerable NP-HARD None of the above

admin asked in Theory of Computation Apr 1, 2020

by admin

551 views

0 votes

4 answers

15

NIELIT 2017 July Scientist B (CS) - Section B: 59
Let $L$ be a language and $L’$ be its complement. Which one of the following is NOT a viable possibility? Neither $L$ nor $L’$ is RE. One of the $L$ and $L’$ is RE but not recursive;the other is not RE. Both $L$ and $L’$ are RE but not recursive. Both $L$ and $L’$ are recursive.

admin asked in Theory of Computation Mar 30, 2020

by admin

735 views

0 votes

3 answers

16

NIELIT 2017 July Scientist B (CS) - Section B: 60
Let $L1$ be a recursive language, and let $L2$ be a recursively enumerable but not recursive language. Which one of the following is TRUE? $L1’$ is recursive and $L2’$is recursively enumerable. $L1’$ is recursive and $L2’$is not recursively enumerable. $L1’$ and $L2’$is recursively enumerable. $L1’$ is recursively enumerable and $L2’$is recursive.

admin asked in Theory of Computation Mar 30, 2020

by admin

822 views

0 votes

4 answers

17

NIELIT 2017 DEC Scientist B - Section B: 19
Recursive enumerable languages are not closed under _________. Set difference Complement Both (A) and (B) None of the options

admin asked in Theory of Computation Mar 30, 2020

by admin

1.4k views

Page:

1
2
3
4
5
6
...
9
next »

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