The Gateway to Computer Science Excellence
+2 votes

# i confirm answer plz check???

in Theory of Computation by
edited by | 175 views
Only 3 and 4 are correct. What is given answer??
all false
Have they given explanation. Plz post it if possible.


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
you are correct.

2 Answers

+2 votes
Best answer

Given answer is 100% correct.

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

Example:L1={anbncm} intersection L2={ambncn}={anbncn}

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={anbncm} is a subset of this language is which is not regular.

selected by

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 ? 

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.
Yes i understand that but then why in the solution it is given that the set of non RE languages are uncountably infinite.
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.
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.

// 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 2sigma * is not countable. 

The set of all TM is countable so yo can understand from it that set of RE is also countable.
Okay ... yeah got it.

Thank you very much
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 Diagonalization method).

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

and for 3rd option....  it is talking about the language not set.


Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,345 questions
60,522 answers
95,372 users