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
1
answer
1
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
by
TusharKumar
115
views
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
1
answer
2
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
218
views
identify-class-language
recursive-and-recursively-enumerable-languages
0
votes
0
answers
3
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
207
views
identify-class-language
recursive-and-recursively-enumerable-languages
3
votes
2
answers
4
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
270
views
theory-of-computation
context-sensitive
recursive-and-recursively-enumerable-languages
1
vote
1
answer
5
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
1.3k
views
nielit2022apr-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
4
votes
2
answers
6
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
8.8k
views
gatecse-2022
theory-of-computation
identify-class-language
recursive-and-recursively-enumerable-languages
multiple-selects
1-mark
9
votes
3
answers
7
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
4.6k
views
gatecse-2021-set1
multiple-selects
theory-of-computation
recursive-and-recursively-enumerable-languages
1-mark
10
votes
5
answers
8
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
6.6k
views
gatecse-2021-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
easy
2-marks
2
votes
2
answers
9
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
1.8k
views
ugcnetcse-oct2020-paper2
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
1
answer
10
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
359
views
nielit2017oct-assistanta-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
4
answers
11
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
473
views
nielit2017july-scientistb-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
3
answers
12
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
603
views
nielit2017july-scientistb-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
4
answers
13
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.1k
views
nielit2017dec-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
2
answers
14
NIELIT 2017 DEC Scientist B - Section B: 27
If any string of a language $L$ can be effectively enumerated by an enumerator in a lexicographic order then language $L$ is _______. Regular Context free but not necessarily regular Recursive but not necessarily context free Recursively enumerable but not necessarily recursive
Lakshman Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
746
views
nielit2017dec-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
3
answers
15
NIELIT 2017 DEC Scientist B - Section B: 32
The collection of Turing recognizable languages are closed under: Union Intersection Complement Concatenation Star Closure (i) Only Both (i),(iv) (i),(ii),(iv)and(v) All of the options
Lakshman Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
1.1k
views
nielit2017dec-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
1
vote
2
answers
16
NIELIT 2017 DEC Scientist B - Section B: 58
Which of the following is a correct hierarchical relationships of the following where $L_1$: set of languages accepted by NFA $L_2$: set of languages accepted by DFA $L_3$: set of languages accepted by DPDA $L_4$: set of languages ... $L_1\subset L_2\subset L_3\subset L_4\subset L_6\subset L_5$
Lakshman Bhaiya
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Bhaiya
907
views
nielit2017dec-scientistb
theory-of-computation
identify-class-language
recursive-and-recursively-enumerable-languages
3
votes
0
answers
17
Michael Sipser Edition 3 Exercise 5 Question 36 (Page No. 242)
Say that a $CFG$ is minimal if none of its rules can be removed without changing the language generated. Let $MIN_{CFG} = \{\langle G \rangle \mid \text{G is a minimal CFG}\}$. Show that $MIN_{CFG}$ is $T-$recognizable. Show that $MIN_{CFG}$ is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
505
views
michael-sipser
theory-of-computation
context-free-grammar
recursive-and-recursively-enumerable-languages
decidability
proof
1
vote
0
answers
18
Michael Sipser Edition 3 Exercise 5 Question 35 (Page No. 242)
Say that a variable $A$ in $CFG \:G$ is necessary if it appears in every derivation of some string $w \in G$. Let $NECESSARY_{CFG} = \{\langle G, A\rangle \mid \text{A is a necessary variable in G}\}$. Show that $NECESSARY_{CFG}$ is Turing-recognizable. Show that $NECESSARY_{CFG} $is undecidable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Bhaiya
274
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
proof
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 5 Question 24 (Page No. 240)
Let $J = \{w \mid \text{either $w = 0x$ for some $x \in A_{TM},$ or $w = 1y\:$ for some $y \in \overline{A_{TM}}\:\:$}\}$. Show that neither $J$ nor $\overline{J}$ is Turing-recognizable.
Lakshman Bhaiya
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Bhaiya
139
views
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
Page:
1
2
3
4
5
6
...
8
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
IIITA M.TECH IT COMPLETE EXPLANATION FROM ADMISSION TO PLACEMENT
GO Classes NIELIT Test Series For 2023
Interview Experience : MTech Research(Machine Learning) at IIT Mandi
DRDO Scientist -B
ISRO Scientist-B 2023
Subjects
All categories
General Aptitude
(2.8k)
Engineering Mathematics
(9.8k)
Digital Logic
(3.4k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.4k)
Others
(2.5k)
Admissions
(667)
Exam Queries
(1.0k)
Tier 1 Placement Questions
(17)
Job Queries
(77)
Projects
(9)
Unknown Category
(867)
Recent questions tagged recursive-and-recursively-enumerable-languages
Recent Blog Comments
This story is same like my tier 3 college btech...
@Nikhil_dhamaHi , now i am in 2nd semester...
You can attempt now:...
where is the free test link ? how i can attempt...
Left with 10days, nothing heard back from them,...