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
1
vote
1
answer
1
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
by
soujanyareddy13
263
views
nielit2022apr-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
4
votes
2
answers
2
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
by
Arjun
4.1k
views
gatecse-2022
theory-of-computation
identify-class-language
recursive-and-recursively-enumerable-languages
multiple-selects
1-mark
9
votes
3
answers
3
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
3.5k
views
gatecse-2021-set1
multiple-selects
theory-of-computation
recursive-and-recursively-enumerable-languages
1-mark
8
votes
5
answers
4
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
4.7k
views
gatecse-2021-set1
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
easy
2-marks
2
votes
2
answers
5
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.5k
views
ugcnetcse-oct2020-paper2
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
1
answer
6
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 Patel RJIT
asked
in
Theory of Computation
Apr 1, 2020
by
Lakshman Patel RJIT
306
views
nielit2017oct-assistanta-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
4
answers
7
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 Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
397
views
nielit2017july-scientistb-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
3
answers
8
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 Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
504
views
nielit2017july-scientistb-cs
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
4
answers
9
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 Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
960
views
nielit2017dec-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
2
answers
10
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 Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
658
views
nielit2017dec-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
0
votes
3
answers
11
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 Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
958
views
nielit2017dec-scientistb
theory-of-computation
recursive-and-recursively-enumerable-languages
1
vote
2
answers
12
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 Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
759
views
nielit2017dec-scientistb
theory-of-computation
identify-class-language
recursive-and-recursively-enumerable-languages
3
votes
0
answers
13
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 Patel RJIT
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Patel RJIT
468
views
michael-sipser
theory-of-computation
context-free-grammar
recursive-and-recursively-enumerable-languages
decidability
proof
1
vote
0
answers
14
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 Patel RJIT
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Patel RJIT
253
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
proof
0
votes
0
answers
15
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 Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
113
views
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
16
Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
107
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
reduction
proof
0
votes
0
answers
17
Michael Sipser Edition 3 Exercise 5 Question 7 (Page No. 239)
Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 19, 2019
by
Lakshman Patel RJIT
150
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
reduction
proof
0
votes
0
answers
18
Michael Sipser Edition 3 Exercise 5 Question 2 (Page No. 239)
Show that $EQ_{CFG}$ is co-Turing-recognizable.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 17, 2019
by
Lakshman Patel RJIT
126
views
michael-sipser
theory-of-computation
context-free-grammar
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
19
Michael Sipser Edition 3 Exercise 4 Question 30 (Page No. 212)
Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\{ \langle M_{1}\rangle,\langle M_{2}\rangle,\dots\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not ... $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 17, 2019
by
Lakshman Patel RJIT
238
views
michael-sipser
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
decidability
proof
0
votes
0
answers
20
Michael Sipser Edition 3 Exercise 4 Question 20 (Page No. 212)
Let $A$ and $B$ be two disjoint languages. Say that language $C$ separates $A$ and $B$ if $A \subseteq C$ and $B \subseteq \overline{C}$. Show that any two disjoint co-Turing-recognizable languages are separable by some decidable language.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 17, 2019
by
Lakshman Patel RJIT
248
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
proof
0
votes
0
answers
21
Michael Sipser Edition 3 Exercise 4 Question 18 (Page No. 212)
Let $C$ be a language. Prove that $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y (\langle{ x, y \rangle} \in D)\}$.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 17, 2019
by
Lakshman Patel RJIT
93
views
michael-sipser
theory-of-computation
recursive-and-recursively-enumerable-languages
decidability
proof
Page:
1
2
3
4
5
6
...
8
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
Life happens, just chill and do hardwork
ISRO RECRUITMENT FOR SCIENTIST B THROUGH GATE
POWER GRID CORPORATION OF INDIA LIMITED
INSTITUTE OF BANKING PERSONNEL SELECTION
GATE Overflow books for TIFR, ISRO, UGCNET and NIELIT
Subjects
All categories
General Aptitude
(2.4k)
Engineering Mathematics
(9.1k)
Digital Logic
(3.2k)
Programming and DS
(5.8k)
Algorithms
(4.5k)
Theory of Computation
(6.6k)
Compiler Design
(2.3k)
Operating System
(4.9k)
Databases
(4.5k)
CO and Architecture
(3.7k)
Computer Networks
(4.5k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(648)
Exam Queries
(841)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(855)
Recent questions tagged recursive-and-recursively-enumerable-languages
Recent Blog Comments
The counts of answered, marked etc in the exam...
Tests have been sent and all tests will be...
@GO Classes @Deepak Poonia @Sachin...
@GO Classes @Deepak Poonia sir...
Maximum age limit changed from 35 yrs. to 28...