Question

Using Cantor's Diagonal argument, show that for a given alphabet A, the set of possible DFAs is countably infinite (that is, it’s the same as the number of natural numbers) while the set of all possible languages is uncountably infinite (that is, it’s as large as the number of subsets of the natural numbers)

Answer 1

1) _DEA DEA is is a 5- tuple M=(0, E,S, 90, F) 191<0 & 8 to E is alphabet 8 : * £ $ got 8 initial state Fs & Accepted states is Number of no influence For each of 8's is countable because there of name of states on DFA number of OFA is finite Hence, the set of all DFAS is countable (ii) alphabets. A word is Let w be any the finite sequence of set of all words Wn := words with a sequence of length n. Llwnl=IEI" W = u Wa n=1 As all Wn's are finite ... W is at most countable It is countable because Wn x WinWj = 6 x izja 6 & nyl .. we can have where one word a bijection from is linked with a w to N. notural numbe rural number A_language L&W.

" Set of all languages = ges = P(W) [Power set of w ) le (W) 1 = |P(IN)! An element of P(IN) can be denoted by an infinite sequence of o's R l's. where position of I would de note that that number is in the element Ro would indicate the otherwise. IS PIN) is countable then we can list it's elements - d, diz diz .. dzi du daz... die diz diz ... Now we will consider the number - di dzz dzz... die ... ننه - ا = هههه اها in our list contradiction at kth that If we have this number - number then we get a - clee # dee = It is not in the list Hence, our assumption that P(N) is countable _was wrong

Cantor's argument can directly be applied on P(W).

Words are listed( as they are countable it is possible).

Where 1 would signify that the word is in the language and 0 would signify that word is not in the language.