Is the set of nonregular languages larger than the set of regular languages?

[brian44]

I was wondering, since the size of complementary sets comes up often in other areas of math, e.g. the set of rational numbers is countably infinite but set of irrationals is uncountably infinite, so that the set of irrationals is in some sense "larger" than rationals.

Does a similar kind of relationship exist for the set of all regular languages and the set of all nonregular languages over any given alphabet (referring to theory of computation and finite automata)?

My feeling is that the set of nonregular languages should be larger in some sense, but I don't know if this is correct nor how to prove it, nor what types of classes the two sets belong to, since it seems possible they could both be uncountably infinite, but I believe there are degrees of size beyond uncountably infinite getting into transcendental numbering or something that I have not yet read about.

 

[Hurkyl]

The set of finite automata is countable. The set of languages is not.

 

[brian44]

Thanks I see now how the first part is obvious:

Even if we don't fix the alphabet, the set of all finite automata is a countable union of at most countable sets and hence is at most countable. Therefore the set of regular languages, those that can be recognized by some finite automata, is at most countable.

But how do you prove the set of languages is uncountable? At first I thought to do it by saying:

The set of all languages is uncountable because we can construct an uncountable set of languages that is a subset of the set of all languages as follows.
The set of all strings over the alphabet {0,1,...,9} has the same cardinality as the set of all decimal expansions of the real numbers in [0,1]. If we take each string to define its own language, then the set of these languages is uncountable.
However I think this is incorrect because strings are defined to be finite sequences of symbols from the alphabet.

 

[Hurkyl]

The set of strings is countable. The set of languages is the power set of the set of strings.