- #1
brian44
- 23
- 0
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.
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.