Subset of a language in Regular Expression

(1) Subset of a language in RE is always RE.

(2) A language is not RE is uncountably infinite.

 

statements are true/false and why?

5Comments
Ashish Kumar Goyal @dashish
30 Jan 2017 06:20 pm
1st->false and 2nd->true....
A regular language is not closed under subset operation.
and any finite language is regular. regular contains all finite languages and some infinite. so, a lang not RE is obviously infinite
Shobhit @sudsho
30 Jan 2017 08:38 pm

^ how second one is true?

Ashish Kumar Goyal @dashish
30 Jan 2017 08:54 pm

@sudsho

any finite language is regular and a FA can be designed for it. So a lang not regular is definately infinite.

Shobhit @sudsho
30 Jan 2017 09:16 pm

language not regular is definitly infinite...fine
(2) A language is not RE is uncountably infinite.
there is no difference between countable infinite and uncountable infinite?

Shobhit @sudsho
30 Jan 2017 09:29 pm

(1) Subset of a language in RE is always RE.
false..RE are not closed under subset operation

(2) A language is not RE is uncountably infinite
false...we know that sigma star is countable...a language is nothing but a subset of sigma star..every subset of a countable set is countable..hence all languages are countable...though set of languages which are not RE are uncountable....mind my word here.."set"

Pages