1,250 views

2 Answers

0 votes
0 votes

we can prove that set of all strings over any infinite alphabet(as said more than one symbol)  is uncountable by proper ordering.  we will see that even to generate  a string of length k  would not be any enumeration possible in finite steps. hence set of L ⊊ ∊*  so L is uncountable.  

now set of all languages = power set of of    *    i.e 2 ^(*)  and we can prove that if S is countable then power set of set of S is uncountable by diagonalization. so oviously if  S is uncountable as here then power set of S is uncountable 

But, i am not sure as just not getting enumeration method is not enough to conclude that it is uncountable as there may exist other.but i dont think using proper ordering we will get enumeration hence i concluded that it cant be enumerated.   

0 votes
0 votes
can give a informal proof to remember. the set of all string of a language is countable where as the set of all languages is uncountable because we can put all the string is proper odering and then they can be enumerated . while suppose you yake set of all languages now even first language will be having infinite strings. like the case of real number . so u will never reach the language 2 . this he informal proof formal proof is diagonalization method.

Related questions

0 votes
0 votes
0 answers
1
koushriek asked May 19, 2022
1,280 views
Examples of accepted words: 1011, 101101, 1111Example of non-accepted words: 101, 1001, 010The solution says the min-DFA contains 5 states but I could only do it in 4. Am...