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

In summary, The conversation is discussing the relationship between the size of complementary sets in different areas of math, specifically the set of rational numbers and the set of irrationals, and whether a similar relationship exists for the set of regular and nonregular languages in the theory of computation. While the set of finite automata is countable, the set of languages is not, and it can be proven by constructing an uncountable subset of languages using decimal expansions of real numbers. However, this approach may be incorrect because strings are defined as finite sequences.
  • #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.
 
Mathematics news on Phys.org
  • #2
The set of finite automata is countable. The set of languages is not.
 
  • #3
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.
 
  • #4
The set of strings is countable. The set of languages is the power set of the set of strings.
 

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

1. What is the difference between regular and nonregular languages?

Regular languages are a type of formal language that can be recognized by a deterministic finite automaton. Nonregular languages are formal languages that cannot be recognized by a deterministic finite automaton.

2. How do we determine if a language is regular or nonregular?

A language is regular if it can be recognized by a deterministic finite automaton. On the other hand, a language is nonregular if it cannot be recognized by a deterministic finite automaton.

3. Are there more regular or nonregular languages?

There are infinitely many regular languages and infinitely many nonregular languages. However, the set of regular languages is smaller than the set of nonregular languages.

4. Why is the set of nonregular languages larger than the set of regular languages?

The set of regular languages is smaller because the rules for regular languages are more restrictive. Nonregular languages have more complex and varied structures that cannot be recognized by a deterministic finite automaton.

5. Can nonregular languages be converted into regular languages?

No, nonregular languages cannot be converted into regular languages. This is because regular languages have simpler structures and can be recognized by a deterministic finite automaton, while nonregular languages have more complex structures that cannot be recognized by a deterministic finite automaton.

Similar threads

Replies
15
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
2
Views
314
Replies
85
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
16
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
599
  • Engineering and Comp Sci Homework Help
Replies
1
Views
2K
Replies
31
Views
5K
Back
Top