1
$\begingroup$

I'm trying to figure out how to prove or disprove the following statement:

Infinite union of recursive languages is recursively enumerable.

I know how to prove that infinite union of regular languages is not recursive, but I can't figure out how to prove the statement above. Intuition is telling me that the statement is true, but I'm not sure. Does anybody know how would I go about it?

Any help is greatly appreciated.

$\endgroup$
  • 3
    $\begingroup$ Consider the infinite usion of languages of the form $\{w\}$, i.e., each containing a single word. $\endgroup$ – Hendrik Jan Nov 12 '13 at 0:29
  • $\begingroup$ @HendrikJan: I think this will just tell me that infinite set of recursive languages is not recursive. What I need to show that infinite set is recursively enumerable (or not). $\endgroup$ – flashburn Nov 12 '13 at 0:32
  • 3
    $\begingroup$ Why would $\bigcup_{w\in L} \{w\}$ be RE? $\endgroup$ – Hendrik Jan Nov 12 '13 at 0:36
  • $\begingroup$ @HendrikJan: I realize that my answer might sound stupid, but would you mind explaining why it is not RE? My professor is not very good at explaining the material and I would greatly appreciate any help. $\endgroup$ – flashburn Nov 12 '13 at 0:38
  • $\begingroup$ Not every language $L$ is RE. $\endgroup$ – Hendrik Jan Nov 12 '13 at 0:41
5
$\begingroup$

Choose an arbitrary language $L$ that is not RE. Denote $L_w=\{w\}$ the language containing a single word $w$. Clearly, $L=\bigcup_{w\in L} L_w$ is a union of infinitely many regular and recursive languages.

$\endgroup$
  • $\begingroup$ I think I'm missing something. I realize that this question might sound strange to someone but as I said my professor is not very good at explaining the material. My question is why I can make an assumption that I can choose a non RE language such that it is a union of regular languages? $\endgroup$ – flashburn Nov 12 '13 at 13:39
  • $\begingroup$ @flashburn, I'm disproving the statement "for all infinite sets of recursive languages, their union is RE" by showing a counterexample. In this case, I'm saying "look, here's one concrete language $L$ and and infinite set of regular languages $L_w$ whose union is $L$". Sure, I didn't actually say what $L$ is, but that's not really a problem -- all you need to prove is that there is at least one (and we kinda know that there is :) ). $\endgroup$ – avakar Nov 12 '13 at 14:27
  • $\begingroup$ @flashburn This works for the following reason: (1) Not every language is RE; (2) Every language can be expressed as an infinite union of languages containing a single word; (3) therefore, there are languages that are not RE that can be expressed as an infinite union of languages containing a single word. Similarly: (1) Not all mammals are people; (2) All mammals are living things; (3) therefore, there are mammals that aren't people that are living things. $\endgroup$ – Patrick87 Nov 12 '13 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.