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

32 views Asked by At

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.

0

There are 0 answers