Recursive and Recursively Enumerable

Question

A language in NOT - RE is un-countably infinite. true or false? pls elaborate the answer you post.

Comments

every language either RE OR NOT RE is a subset of (0+1)* and hence either a countable set or finite set in case its not finite its countable

Answer 1

All the strings in the language are enumerated whether it is RE or NOT RE.

Every language can be enumerated because language has finite length strings. And if i start from smallest string in the language and move to the next greater length and so on.Then i can map all the strings to the Natural numbers.For e.g if there is any two length and three length string in language ,then no other length string can come in between.As all the string length is discrete so it is possible to map it to natural numbers.

Hence every language whether it is RE or not ,it is always countable.So the statement is false.

Not RE will always be countable infinite.

Why not finite? Because finite is regular

Why not uncountable? As every language is countable.

Hence,given statement is false

Comments

what is meant by enumerated . Give an example plz.

---

Enumeration is nothing but arranging the strings in given order.

For example you can enumerate the strings in increasing length. Like len 0, the len 1 the len 2 and so on.

@rahul sharma 5 what is the type of lang L ={ set of real numbers between 0 and 1} because this lang is uncountably infinite.

---

@Subhanshu,isnt it regular? Regular expression:  $(0+1)^* $ + $(0+1)^* . (0+1)^* $

1 length string:- 0,1

2 length string:- 00,11,01,10

3 length:- 000,111,0.0,1,1.....

Actually here we need to compare length instead of number themselves.I can say there is no string between length 2 and length 3,right?