Please provide a proof for each question 1 Prove or disprove

Please provide a proof for each question.

1. Prove or disprove: every regular language is countable.

2. Prove or disprove: the set of all regular languages is countable.

3. Prove or disprove: the set of all languages is countable.

Solution

The set of regular languages is countable.
proof:

1)Each regular language is recognized by some DFA.
2)Each DFA has a finite description: states, start states,transitions.
3)Can write each of these using standard names for states, without changing the language.
4)Can enumerate these “standard form” DFAs in order of length.
5) Leads to an enumeration of the regular languages.
6)Since P(*), the set of all languages, is uncountable, whereas the set of regular languages is
countable, some language must be non-regular.
7)In fact, by considering different kinds of infinity, one can prove that “most” languages are non-regular.

-----------------------------------------------------------------------------------------------------------