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

115 views

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

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

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

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

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

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

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

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

1.8k views

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

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

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

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

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

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

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

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

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

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

Page:

1
2
3
4
5
6
...
8
next »

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