284 views
Let L1,L2,L3..... are infinite sequence of regular languages.
$L=\bigcup_{i=1}^{\propto }L_{i}$ which of the following statements is true?

A. L is always regular
B. L is always context free
C. L is always recursive
D. It can be a non recursively enumerable language
0
c???
+1
d will be true
0
@Anu can you explain? @joshi_nitish can you check?
+1

hemant i help you to prove but you have to help me, prove me this may not be regular, then may not be cfl, then may not be csl too.. plz analyse why not they are regular, cfl, csl

you can do it , if till csl you do it then we can say it may not be even non re

+5

yes, D) is correct.

let some non recursively language L = {aaa, abbbab, ba, baaaba, baaabbaba,......... }

now L1= {aaa} , L2={abbbab}, L3={ba}, L4={baaaba}, L5={baaabbaba}.......//see all of these are regular since finite.

now L$\cup$ L2 $\cup$ L3 $\cup$ L4 $\cup$ L5.......=L(non recursively enurable)

hence you can see that, infinite union of regular languages in worst case can be Non REL.

+3

Take a non-enumerable language L and the infinitely many (regular) singleton sets that contain exactly one word from this language. Their union is L and thus non-enumerable.

https://stackoverflow.com/questions/38893423/infinite-union-of-regular-language

+1
@joish_nitish,

What will be the difference L1, L2, L3 is a finite sequence of a regular language instead of an infinite sequence of regular language?
+1

@Hemant

it is "infinite sequence of regular languages(finite or infinite)"

i think what you are thinking is "sequence of inifinite length regular languages", both are different things

+2
@Hemant If the sequence is finite, then essentially we are doing union finite number of times. The resultant language must be regular. We know that union of 2 regular languages is regular, so the union of finite(say 4) will also be regular.

((L1 U L2) U L3) U L4
+2
Thanks..!! @Rishabh, @joshi_nitish. :)
0
@joshi nitish, can you give any standard example where infinite union of regular is not RE?
0
L is not regular because for constructing a DFA for L it will need infinite number of states which is not possible hence it cannot be regular am i right?