The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+6 votes

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

$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

+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 L_{1}= {aaa} , L_{2}={abbbab}, L_{3}={ba}, L_{4}={baaaba}, L_{5}={baaabbaba}.......//**see all of these are regular since finite**.

now L_{1 }$\cup$ L_{2} $\cup$ L_{3} $\cup$ L_{4} $\cup$ L_{5}.......=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?

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

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,947 questions

41,993 answers

119,239 comments

41,485 users