Register

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

2 2 votes
1 1 answer
398
398 views
TIFR CSE 2025 | Part B | Question: 4
Consider the following languages:$L_{1}$ is the set of languages recognised by a deterministic pushdown automaton.$L_{2}$ is the set of languages recognised by a nondeter...
User Avatar
0 0 votes
1 1 answer
699
699 views
ISRO CSE 2023 | Question: 55
Which of the following statements is NOT true?If a language is recursive its complement is recursiveIf a language is recursive its complement is recursively enumerableIf ...
User Avatar
0 0 votes
0 0 answers
424
424 views
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 a...
User Avatar
1 1 vote
0 0 answers
890
890 views
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 th...
User Avatar
0 0 votes
0 0 answers
735
735 views
UGC NET CSE | June 2023 | Part 2: 2
Which of the following statement is correct?Ackermann's function is primitive recursive.$L=\left\{a^{n} b^{k} c^{n+k}: n \geq 0, k \geq 0\right\}$ is regular language.$L=...
User Avatar
1 1 vote
0 0 answers
398
398 views
UGC NET CSE | June 2023 | Part 2: 74
The set of turning machine codes for $\text{TM's}$ that accept all inputs that are palindromes (possible along with some other inputs) is decidableThe language of codes f...
User Avatar
0 0 votes
1 1 answer
591
591 views
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.?
User Avatar
0 0 votes
1 1 answer
1.3k
1.3k views
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 decidableB.L is undecidableC.Cannot be predi...
User Avatar
0 0 votes
0 0 answers
1.6k
1.6k views
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 decidableB.L is Turing recognizableC.L is not recurs...
User Avatar
1 1 vote
2 answers 2 answers
1.8k
1.8k views
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 thi...
User Avatar
0 0 votes
1 1 answer
512
512 views
UGC NET CSE | October 2022 | Part 1 | Question: 28
Consider the properties of recursively enumerable sets :FinitenessContext FreedomEmptinessWhich of the following is true?Only $(\text{I})$ and $(\text{II})$ are not decid...
User Avatar
0 0 votes
0 0 answers
468
468 views
UGC NET CSE | October 2022 | Part 1 | Question: 32
Consider the properties of recursively enumerable sets :FinitenessContext FreedomEmptinessWhich of the following is true?Only $(\mathrm{I})$ and $(\mathrm{II})$ are not d...
User Avatar
4 4 votes
1 answers 1 answer
4.2k
4.2k views
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...
User Avatar
1 1 vote
0 0 answers
670
670 views
NIELIT 2022 April Scientist B | Section B | Question: 92
$\text{L1}$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $w_1, w_2, w_3, \dots$ Define another language $\text...
User Avatar
24 24 votes
2 answers 2 answers
28.7k
28.7k views
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 $\over...
User Avatar
0 0 votes
1 1 answer
919
919 views
NIELIT 2021 Dec Scientist B - Section B: 52
A language $\text{L}$ is recognizable by a turing machine $\text{M}$ if and only if $\text{L}$ is a _____________ language.Type $0$Type $1$Type $2$Type $3$
User Avatar
0 0 votes
2 answers 2 answers
917
917 views
UGC NET CSE | December 2019 | Part 2 | Question: 50
Consider the following language families:$L_1 \equiv$ The context-free languages$L_2 \equiv$ The context-sensitive languages$L_3 \equiv$ The recursively enumerable langua...
User Avatar
31 31 votes
4 answers 4 answers
16.3k
16.3k views
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= \{ \la...
User Avatar
36 36 votes
6 answers 6 answers
20.9k
20.9k views
GATE CSE 2021 | Set 1 | Question: 39
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...
User Avatar
Page: