Recent questions tagged recursive-and-recursively-enumerable-languages / GATE Overflow for GATE CSE

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?

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 a...

dopq12

91 views

dopq12 asked Mar 5

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$.

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$....

GO Classes

494 views

GO Classes asked Jan 28

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

which of the following statements is NOT true?If a language is recursive it complement is recursiveIf a language is recursive its complement is recursively enumerableIf a...

Ramayya

145 views

Ramayya asked Jan 7

1 votes

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

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 ...

amitarp818

238 views

amitarp818 asked Dec 28, 2023

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.?

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

328 views

TusharKumar asked Jan 21, 2023

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

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 decidableB.L is undecidableC.Cannot be predi...

Rajender gill

514 views

Rajender gill asked Dec 21, 2022

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

Consider the following language:L = {< M | L(M) has atleast 10 strings}Which of the following is true about L?A.L is decidableB.L is Turing recognizableC.L is not recurs...

Rajender gill

508 views

Rajender gill asked Dec 21, 2022

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?

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 ...

h4kr

764 views

h4kr asked Dec 18, 2022

1 votes

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

Consider the following types of languages:$\text{L1}:$ Regular,$\text{L2}:$ Context-free,$\text{L3}:$ Recursive,$\text{L4}:$ Recursively enumerable.Which of the following...

soujanyareddy13

2.9k views

soujanyareddy13 asked Apr 12, 2022

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.

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 $\over...

Arjun

15.3k views

Arjun asked Feb 15, 2022

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 ^* \}$

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= \{ \la...

Arjun

7.3k views

Arjun asked Feb 18, 2021

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

For a Turing machine $M$, $\langle M \rangle$ denotes an encoding of $M$. Consider the following two languages.$$\begin{array}{ll} L_1 = \{ \langle M \rangle \mid M \text...

Arjun

9.9k views

Arjun asked Feb 18, 2021

4 votes

1 answer

13

GATE Overflow Test Series | Mock GATE | Test 5 | Question: 55
Which of the following languages is/are not recursively enumerable? Here, $\langle M \rangle$ denotes an encoding of Turing machine $M.$ (Mark all the appropriate choices) $L = \{\langle M \rangle\mid L(M) \text{ is empty}\}$ ... $L = \{\langle M \rangle\mid L(M) \text{ has at most 2021 strings}\}$

Which of the following languages is/are not recursively enumerable? Here, $\langle M \rangle$ denotes an encoding of Turing machine $M.$ (Mark all the appropriate choices...

gatecse

476 views

gatecse asked Feb 8, 2021

5 votes

1 answer

14

GATE Overflow Test Series | Mock GATE | Test 4 | Question: 63
Consider the following languages. $L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2021 steps on some input} \right\}$ ... $L_{2}$ are recursive and $L_{3}$ is not recursive $L_{1}, L_{2}, L_{3}$ are recursively enumerable

Consider the following languages.$L_{1} = \left\{\left\langle M \right\rangle \mid M \text{ takes at least 2021 steps on some input} \right\}$,$L_{2} = \left\{\left\langl...

gatecse

450 views

gatecse asked Feb 1, 2021

7 votes

1 answer

15

GATE Overflow Test Series | Mock GATE | Test 1 | Question: 44
Which of the following languages is/are recursively enumerable but not recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices) $L = \{\langle M \rangle\mid 0 \in L(M)\}$ ... $L = \{\langle M \rangle\mid L(M) \text{ is recursively enumerable} \}$

Which of the following languages is/are recursively enumerable but not recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the approp...

gatecse

994 views

gatecse asked Jan 3, 2021

2 votes

2 answers

16

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

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$ isRecursively enumerable but n...

go_editor

2.2k views

go_editor asked Nov 20, 2020

6 votes

2 answers

17

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 26
Which of the following languages is/are recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices) $L = \{\langle M \rangle \mid M \text{ moves its head left on input } w\}$ ...

Which of the following languages is/are recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices) $L = \{\langle M...

gatecse

666 views

gatecse asked Sep 29, 2020

5 votes

2 answers

18

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 27
Which of the following languages is/are recursively enumerable but not recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices) $L = \{\langle M \rangle\mid L(M) = \emptyset\}$ ... $L = \{\langle M,w \rangle\mid w \in L(M)\}$

Which of the following languages is/are recursively enumerable but not recursive? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the approp...

gatecse

530 views

gatecse asked Sep 29, 2020

6 votes

2 answers

19

GATE Overflow Test Series | Theory of Computation | Test 1 | Question: 28
Which of the following languages is/are not recursively enumerable? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices) $L = \{\langle M \rangle\mid L(M) = \Sigma^*\}$ ... $L = \{\langle M \rangle\mid L(M) = \emptyset\}$

Which of the following languages is/are not recursively enumerable? Here, $\langle M \rangle$ denote an encoding of Turing machine $M.$ (Mark all the appropriate choices)...

gatecse

399 views

gatecse asked Sep 29, 2020

0 votes

1 answer

20

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

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 beRecurs...

admin

554 views

admin asked Apr 1, 2020

0 votes

4 answers

21

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.

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 bu...

admin

759 views

admin asked Mar 30, 2020

0 votes

3 answers

22

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.

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’$...

admin

839 views

admin asked Mar 30, 2020

0 votes

4 answers

23

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

Recursive enumerable languages are not closed under _________.Set differenceComplementBoth (A) and (B)None of the options

admin

1.4k views

admin asked Mar 30, 2020

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