The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+17 votes

Which of the following three statements are true? Prove your answer.

- The union of two recursive languages is recursive.
- The language $\{O^n \mid n\text{ is a prime} \}$ is not regular.
- Regular languages are closed under infinite union.

+16 votes

Best answer

+4

Yes. Regular languages are closed under finite union, and the proofs runs along the lines that you sketch in the question, however this falls apart under infinite union. We can show this by taking L_{i}={0^{i}1^{i}} for each i (with Σ={0,1}). The infinite union of these languages of course gives the canonical non-regular (context-free) language L={0^{i}1^{i}∣i∈N}.

0

Does infinite union mean, we need to have infinite no. of states which cannot be true for FA thus false?

0

please any one tell me

1.DETERMISTIC CONTEXT FREE LANGUAGE

2.CONTEXT SENSITIVE LANGUAGE

3.RECURSIVE LANGUAGE

4.RECURSIVE ENUMERABLE LANGUAGE

ALL ABOVE ARE BOUND UNDER WHICH OPERATIONS.?

1.DETERMISTIC CONTEXT FREE LANGUAGE

2.CONTEXT SENSITIVE LANGUAGE

3.RECURSIVE LANGUAGE

4.RECURSIVE ENUMERABLE LANGUAGE

ALL ABOVE ARE BOUND UNDER WHICH OPERATIONS.?

0

(i) The union of two recursive languages is recursive.

(ii) The language {On∣n is a prime}{On∣n is a prime} is not regular.

how both are true , can you please explain in detail

(ii) The language {On∣n is a prime}{On∣n is a prime} is not regular.

how both are true , can you please explain in detail

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.7k
- Digital Logic 2.2k
- Programming & DS 4.1k
- Algorithms 3.6k
- Theory of Computation 4.5k
- Compiler Design 1.7k
- Databases 3.2k
- CO & Architecture 2.8k
- Computer Networks 3.2k
- Non GATE 1.1k
- Others 1.5k
- Admissions 503
- Exam Queries 474
- Tier 1 Placement Questions 22
- Job Queries 61
- Projects 13

39,713 questions

46,750 answers

140,552 comments

58,384 users