Register

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

• retagged by
200 views
0 votes
0 votes

 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 languages are closed under the following operations. You may give informal, but clear, constructions to show closure.

  1. Union.
  2. Intersection.
  3. Concatenation.
  4. Kleene closure(star).
  5. Homomorphism.
  6. Inverse homomorphism.
• retagged by
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
4
admin asked Jul 21, 2019
255 views
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...
User Avatar
Link Copied!