Can you prove (or give example) why iii is false?

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.?

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.4k
- Digital Logic 2.1k
- Programming & DS 3.8k
- Algorithms 3.3k
- Theory of Computation 4.1k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1.1k
- Others 1.4k
- Admissions 496
- Exam Queries 443
- Tier 1 Placement Questions 19
- Job Queries 59
- Projects 9

37,111 questions

44,694 answers

127,237 comments

43,753 users