Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
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-Recursively ... 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
58
views
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
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 recursively enumerable ... 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
by
GO Classes
427
views
goclasses2024-mockgate-13
goclasses
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
2-marks
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
by
Ramayya
121
views
theory-of-computation
recursive-and-recursively-enumerable-languages
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
by
amitarp818
216
views
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
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
by
TusharKumar
302
views
theory-of-computation
recursive-and-recursively-enumerable-languages
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
487
views
identify-class-language
recursive-and-recursively-enumerable-languages
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
452
views
identify-class-language
recursive-and-recursively-enumerable-languages
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
725
views
theory-of-computation
context-sensitive
recursive-and-recursively-enumerable-languages
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
nielit2022apr-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
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.8k
views
gatecse-2022
theory-of-computation
identify-class-language
recursive-and-recursively-enumerable-languages
multiple-selects
1-mark
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.1k
views
gatecse-2021-set1
multiple-selects
theory-of-computation
recursive-and-recursively-enumerable-languages
1-mark
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.7k
views
gatecse-2021-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
easy
2-marks
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
by
go_editor
2.1k
views
ugcnetcse-oct2020-paper2
theory-of-computation
recursive-and-recursively-enumerable-languages
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
Lakshman Bhaiya
asked
in
Theory of Computation
Apr 1, 2020
by
Lakshman Bhaiya
536
views
nielit2017oct-assistanta-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
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.
Lakshman Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
718
views
nielit2017july-scientistb-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
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.
Lakshman Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
802
views
nielit2017july-scientistb-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
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
Lakshman Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
1.4k
views
nielit2017dec-scientistb
theory-of-computation
easy
recursive-and-recursively-enumerable-languages
Page:
1
2
3
4
5
6
...
9
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
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
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(24)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(682)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
243k
comments
79.7k
users
Recent questions tagged recursive-and-recursively-enumerable-languages
Recent Blog Comments
Hlo I'm Rupesh I got AIR 3485 in gate CS and AIR...
@Ajay Sasank here is the direct link...
Thank you for the post didi My GATE 2023 & 2024...
I Hope it helps 😊
Today's best post I seen thank you for motivation