0
$\begingroup$

Question

Is Infinite Union of Recursive language is Recursive?

I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct.

My Approach/Doubt

$\text{let}\,\,L_1=abcd \,\,\,L_2=a^2b^2c^2d^2=aabbccdd,L_3=a^3b^3c^3d^3=aaabbbcccddd$

here $L_{1},L_{2},L_{3}\,....\text{are finite hence regular hence recursive}$

let $L_{Iu}=L_1 \,\cup\,L_2\,\cup\,L_3\,\cup........$

but $L_{Iu}=a^{n}b^{n}c^{n} \text{which is recursive }$ .

so can i say that Infinite Union of Recursive language is Recursive

Please help me out

$\endgroup$
1
$\begingroup$

Every finite language is recursive.

Every language can be written as an infinite union of finite languages.

Some language isn't recursive.

$\endgroup$
  • $\begingroup$ sir, that means $\text{none of regular,cfl,csl,recursive and recursive enumerable are closed under Infinite union}$ $\endgroup$ – virat Oct 15 '17 at 11:08
  • $\begingroup$ Right. If a family of languages contains all singletons (i.e., $\{w\}$) and is closed under arbitrary union, then it either contains all languages or all languages except the empty one. $\endgroup$ – Yuval Filmus Oct 15 '17 at 11:16

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.