CODEWITHSUNDEEP
computation-theoryfinite-automatacountable
Cyberpunk2020
Cyberpunk2020

Reputation: 1

What is the flaw in the proof of the countability of the set of finite language?

Let FT be the class of all finite languages over {0,1}.

Suppose FL is countable, so we can enumerate all members of FL as

FL = {L_0, L_1, L_2, ...}

Meanwhile, we also enumerate all strings over the alphabet as

\Sigma^*={w_0, w_1, w_2, ...}

Now consider the diagonal language

D={w_i: w_i is not in L_i, i=0,1,2,...}

which should be a member of FL.

However, for any i, D is not equal to L_i and we have reached a contradiction.

So FT is not countable.

Upvotes: -2

Views: 36

Answers (1)

Mofun
Mofun

Reputation: 1

You don't have a proof that D is finite. If D is infinite, hence NOT a member of FL, you won't get a contradiction. The probability that w_i in L_i is very small (|L_i| over infinity), w_i has a high chance in D.

Upvotes: 0

Related Questions