The Gateway to Computer Science Excellence

+2 votes

0

I don't thin answer given by them is correct. because statement IV . regular language are closed under subset it's counter to there answer

Statement III may or may not be true if language is not RE that is it is not anyone regular, CFG,CSL,RE and even not RE therefore it will belong to 2^$sigma\sum$ therefore it's incorrect explanation

Statement III may or may not be true if language is not RE that is it is not anyone regular, CFG,CSL,RE and even not RE therefore it will belong to 2^$sigma\sum$ therefore it's incorrect explanation

+2 votes

Best answer

Given answer is 100% correct.

1. False : DCFL's are not closed under intersection.

Example:L1={a^{n}b^{n}c^{m}} intersection L2={a^{m}b^{n}c^{n}}={a^{n}b^{n}c^{n}}

2.False: RE is not closed under complement. What does this mean?? It means that the complement may or may not be RE. It is not certain that it will not be RE.

3.False: All languages are countable. Set of languages may be uncountable.

4.False: No language is closed under subset// this reason is correct.

Someone is commented that reguar languages are closed under subset. No, they are not. L=sigma * is regular right? L1={a^{n}b^{n}c^{m}} is a subset of this language is which is not regular.

0

The third statment given in the question is

III) A language NOT RE is uncountably infinite.

In the solution they explained that

III) All languages are countable, but the **set of NON RE languages are uncountably infinite.**

Isnt that the same thing ?

0

See...a language is a set of strings. And that set is always countable.

They are talking about set of languages. That is not countable.

They are talking about set of languages. That is not countable.

0

Yes i understand that but then why in the solution it is given that the set of non RE languages are uncountably infinite.

0

They are just saying that it is not a language in not RE which is uncountable, it the set of not RE languages which is uncountable.

0

Mam listen,

The question was,

A language in NOT RE is uncountably infinite.

The answer is given as

False, all languages are countable, but the set of NON RE languages is uncountably infinite.

So isnt that the same thing which was asked ?

I mean on one hand they are saying that the statment is false, on the other hand they are saying The set of NON RE languages is uncountably infinite. Both contrdict!

The question was,

A language in NOT RE is uncountably infinite.

The answer is given as

False, all languages are countable, but the set of NON RE languages is uncountably infinite.

So isnt that the same thing which was asked ?

I mean on one hand they are saying that the statment is false, on the other hand they are saying The set of NON RE languages is uncountably infinite. Both contrdict!

0

okay.

The question was,

A **language** in NOT RE is uncountably infinite.

// Meaning: a not RE** language** is uncountably infinite.

The answer is given as

False, all **languages** are countable,so, not RE **Language** is also countable.

but the "**SET"** of NON RE languages is uncountably infinite.

// It is like sigma * is countable but 2^{sigma * }is not countable.

0 votes

let sigma=(a1,a2,a3,......) as input symbols ,

1.then **sigma*** represent the set of all the possible combinations of input symbols (i.e set of all the strings) and we know that ** sigma*** is a countable set(proven with

2. we know that any **language** is the set of strings, means it is the subset of **sigma* **(subset of a countable set is also countable) therefor, **all the languages are countable**. but the set of * Not RE languages *is

and for *3rd option....*** **it is talking about the

52,345 questions

60,522 answers

201,951 comments

95,372 users