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.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,734 questions

47,462 answers

145,528 comments

62,224 users