Register

Ullman (TOC) Edition 3 Exercise 9.2 Question 5 (Page No. 392)

153 views
0 votes
0 votes
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.
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
2
admin asked Jul 21, 2019
179 views
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 $...
User Avatar
Link Copied!