Recent questions tagged recursive-and-recursively-enumerable-languages / GATE Overflow for GATE CSE

0 votes

2 answers

31

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

If any string of a language $L$ can be effectively enumerated by an enumerator in a lexicographic order then language $L$ is _______.RegularContext free but not necessari...

admin

1.1k views

admin asked Mar 30, 2020

0 votes

3 answers

32

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

The collection of Turing recognizable languages are closed under:UnionIntersectionComplementConcatenationStar Closure(i) OnlyBoth (i),(iv)(i),(ii),(iv)and(v)All of the op...

admin

1.5k views

admin asked Mar 30, 2020

1 votes

2 answers

33

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$

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$: ...

admin

1.4k views

admin asked Mar 30, 2020

3 votes

0 answers

34

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.

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 CF...

admin

634 views

admin asked Oct 20, 2019

1 votes

0 answers

35

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.

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...

admin

338 views

admin asked Oct 20, 2019

0 votes

0 answers

36

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.

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 Tur...

admin

212 views

admin asked Oct 19, 2019

0 votes

0 answers

37

Michael Sipser Edition 3 Exercise 5 Question 22 (Page No. 240)
Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

Show that $A$ is Turing-recognizable iff $A \leq_{m} A_{TM}$.

admin

169 views

admin asked Oct 19, 2019

0 votes

0 answers

38

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.

Show that if $A$ is Turing-recognizable and $A\leq_{m} \overline{A},$ then $A$ is decidable.

admin

238 views

admin asked Oct 19, 2019

0 votes

0 answers

39

Michael Sipser Edition 3 Exercise 5 Question 2 (Page No. 239)
Show that $EQ_{CFG}$ is co-Turing-recognizable.

Show that $EQ_{CFG}$ is co-Turing-recognizable.

admin

176 views

admin asked Oct 17, 2019

0 votes

0 answers

40

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$.)

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 ...

admin

313 views

admin asked Oct 17, 2019

0 votes

0 answers

41

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.

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-Tu...

admin

304 views

admin asked Oct 17, 2019

0 votes

0 answers

42

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)\}$.

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)\}$.

admin

175 views

admin asked Oct 17, 2019

0 votes

0 answers

43

Michael Sipser Edition 3 Exercise 4 Question 5 (Page No. 211)
Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.

Let $E_{TM} = \{\langle{ M \rangle } \mid M\: \text{is a TM}\: \text{and}\: L(M) = \phi\}$. Show that $E_{TM}$, the complement of $E_{TM}$, is Turing-recognizable.

admin

138 views

admin asked Oct 17, 2019

0 votes

0 answers

44

Michael Sipser Edition 3 Exercise 3 Question 20 (Page No. 190)
Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.

Show that single-tape $TMs$ that cannot write on the portion of the tape containing the input string recognize only regular languages.

admin

158 views

admin asked Oct 15, 2019

0 votes

0 answers

45

Michael Sipser Edition 3 Exercise 3 Question 19 (Page No. 190)
Show that every infinite Turing-recognizable language has an infinite decidable subset.

Show that every infinite Turing-recognizable language has an infinite decidable subset.

admin

191 views

admin asked Oct 15, 2019

0 votes

0 answers

46

Michael Sipser Edition 3 Exercise 3 Question 17 (Page No. 189)
Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable language $C$ consisting of $TM$ descriptions such that every machine described in $B$ has an equivalent machine in $C$ and vice versa.

Let $B = \{\langle {M_{1}\rangle},\langle{ M_{1}\rangle} , \dots \}$ be a Turing-recognizable language consisting of $TM$ descriptions. Show that there is a decidable la...

admin

129 views

admin asked Oct 15, 2019

0 votes

0 answers

47

Michael Sipser Edition 3 Exercise 3 Question 16 (Page No. 189)
Show that the collection of Turing-recognizable languages is closed under the operation of union. concatenation. star. intersection. homomorphism.

Show that the collection of Turing-recognizable languages is closed under the operation ofunion.concatenation.star.intersection.homomorphism.

admin

160 views

admin asked Oct 15, 2019

0 votes

0 answers

48

Michael Sipser Edition 3 Exercise 3 Question 14 (Page No. 189)
A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end and read only at the right-hand end. ... at any time. Show that a language can be recognized by a deterministic queue automaton iff the language is Turing-recognizable.

A queue automaton is like a push-down automaton except that the stack is replaced by a queue. A queue is a tape allowing symbols to be written only on the left-hand end a...

admin

352 views

admin asked Oct 15, 2019

0 votes

0 answers

49

Michael Sipser Edition 3 Exercise 3 Question 13 (Page No. 189)
A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,S\}$ At each ... that this Turing machine variant is not equivalent to the usual version. What class of languages do these machines recognize?

A Turing machine with stay put instead of left is similar to an ordinary Turing machine, but the transition function has the form$$\delta: Q\times \Gamma \rightarrow Q\ti...

admin

201 views

admin asked Oct 15, 2019

0 votes

0 answers

50

Michael Sipser Edition 3 Exercise 3 Question 12 (Page No. 189)
A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form $\delta: Q\times \Gamma \rightarrow Q\times \Gamma \times \{R,RESET\}$ ... to move the head one symbol left. Show that Turing machines with left reset recognize the class of Turing-recognizable languages.

A Turing machine with left reset is similar to an ordinary Turing machine, but the transition function has the form$$\delta: Q\times \Gamma \rightarrow Q\times \Gamma \ti...

admin

493 views

admin asked Oct 15, 2019

0 votes

0 answers

51

Michael Sipser Edition 3 Exercise 3 Question 11 (Page No. 189)
A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion ... tape as it moves leftward. Show that this type of Turing machine recognizes the class of Turing-recognizable languages.

A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as well as to the right. The tape is initially f...

admin

240 views

admin asked Oct 15, 2019

0 votes

0 answers

52

Michael Sipser Edition 3 Exercise 3 Question 6 (Page No. 188)
In Theorem $3.21$, we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn't we use the following simpler algorithm for the forward direction of the proof? As before, $s_{1}, s_{2},\dots $ is a list of all strings in ... $i = 1,2,3,\dots.$ Run $M$ on $s_{i}.$ If it accepts, print out $s_{i}."$

In Theorem $3.21$, we showed that a language is Turing-recognizable iff some enumerator enumerates it. Why didn’t we use the following simpler algorithm for the forward...

admin

364 views

admin asked Oct 15, 2019

0 votes

0 answers

53

Ullman (TOC) Edition 3 Exercise 9.3 Question 8 (Page No. 401)
Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE. The set of all $TM$ codes for $TM's$ that halt on every input. The set of all $TM$ codes for $TM's$ that halt on no input. The set of ... halt on at least one input. The set of all $TM$ codes for $TM's$ that fail to halt on at least one input.

Tell whether each of the following are recursive, RE-but-not-recursive, or non-RE.The set of all $TM$ codes for $TM's$ that halt on every input.The set of all $TM$ codes ...

admin

236 views

admin asked Jul 21, 2019

0 votes

0 answers

54

Ullman (TOC) Edition 3 Exercise 9.3 Question 7 (Page No. 400 - 401)
Show that the following problems are not recursively enumerable: The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt. The set of pairs $(M_{1},M_{2})$ ... $TM's$.

Show that the following problems are not recursively enumerable:The set of pairs $(M,w)$ such that $TM \ M$, started with input $w$, does not halt.The set of pairs $(M_{1...

admin

257 views

admin asked Jul 21, 2019

0 votes

0 answers

55

Ullman (TOC) Edition 3 Exercise 9.3 Question 5 (Page No. 400)
Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $L$ is $RE$, but recursive.

Let $L$ be the language consisting of pairs of $TM$ codes plus an integer, $(M_{1},M_{2},k)$, such that $L(M_{1})\cap L(M_{2})$ contains at least $k$ strings. Show that $...

admin

179 views

admin asked Jul 21, 2019

0 votes

0 answers

56

Ullman (TOC) Edition 3 Exercise 9.2 Question 6 (Page No. 392)
We have not discussed closure properties of the recursive languages or the RE languages other than our discussion of complementation in Section $9.2.2.$ Tell whether the recursive languages and/or the RE ... , constructions to show closure. Union. Intersection. Concatenation. Kleene closure(star). Homomorphism. Inverse homomorphism.

We have not discussed closure properties of the recursive languages or the RE languages other than our discussion of complementation in Section $9.2.2.$ Tell whether the ...

admin

201 views

admin asked Jul 21, 2019

0 votes

0 answers

57

Ullman (TOC) Edition 3 Exercise 9.2 Question 5 (Page No. 392)
Let $L$ be recursively enumerable and let $\overline{L}$ be non-RE. Consider the language $L' = \left\{0w\mid w\ \text{is in}\ L \right\}$ Can you say for certain whether $L'$ or its complement are recursive, RE, or non-RE? Justify your answer.

Let $L$ be recursively enumerable and let $\overline{L}$ be non-RE. Consider the language$L' = \left\{0w\mid w\ \text{is in}\ L \right\}$Can you say for certain whether $...

admin

154 views

admin asked Jul 21, 2019

0 votes

0 answers

58

Ullman (TOC) Edition 3 Exercise 9.2 Question 4 (Page No. 391)
Let $L_{1},L_{2},\cdot\cdot\cdot,L_{k}$ be a collection of languages over alphbet $\Sigma$ such that: For all $i\neq j$, $L_{i}\cap L_{j}=\phi$ ... languages $L_{i}$, for $i=1,2,\cdot\cdot\cdot,k$ is recursively enumerable. Prove that each of the languages is therefore recursive.

Let $L_{1},L_{2},\cdot\cdot\cdot,L_{k}$ be a collection of languages over alphbet $\Sigma$ such that:For all $i\neq j$, $L_{i}\cap L_{j}=\phi$; i.e., no string is in two ...

admin

215 views

admin asked Jul 21, 2019

0 votes

1 answer

59

Ullman (TOC) Edition 3 Exercise 9.2 Question 3 (Page No. 391)
Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ ... $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$.

Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10...

admin

616 views

admin asked Jul 21, 2019

0 votes

1 answer

60

Self Doubt: Decidability
$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$ is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \right )$ signifies language $L\left ( M_{1} \right )$ is reducible to $L\left ( M_{2} \right )$

$L=\left \{\langle M_{1},M_{2}\rangle \text{ such that L}(M_{1})\prec L(M_{2}) \right \}$is it recursive enumerable? here $L\left ( M_{1} \right )\prec L\left ( M_{2} \ri...

ajaysoni1924

856 views

ajaysoni1924 asked Jul 15, 2019

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