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.(adsbygoogle = window.adsbygoogle || []).push({});

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.

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

Loading...

Similar Threads - nonregular languages larger | Date |
---|---|

A Find a circle inside of and tangent to a larger circle | Sep 23, 2017 |

Insights FME in Probability - Conditionals in Natural Language - Comments | May 22, 2015 |

Homomorphisms of Languages | Jul 31, 2013 |

Please, Help Me Learn Math's Language! | May 18, 2012 |

Weird Integer Progression in Language Whose Name I Failed to Catch | Nov 23, 2011 |

**Physics Forums - The Fusion of Science and Community**