The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+6 votes
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
asked in Theory of Computation by Boss (15.2k points) | 284 views
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?

Please log in or register to answer this question.

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

40,734 questions
47,462 answers
145,528 comments
62,224 users