Definition of a regular language

Question

I'm a little confused by Wikipedia's definition of a regular language:

The collection of regular languages over an alphabet $\Sigma$ is defined recursively as follows:

• The empty language $\emptyset$ is a regular language.
• For each $a \in \Sigma$ ($a$ belongs to $\Sigma$), the singleton language ${a}$ is a regular language.
• If $A$ and $B$ are regular languages, then $A \cup B$ (union), $A \cdot B$ (concatenation), and $A^\ast$ (Kleene star) are regular languages.
• No other languages over $\Sigma$ are regular.

This seems defines a regular language as any set that contains a finite number of unique elements, though the set can be countably infinite (it's worth noting that the article doesn't explicitly state that $\left\vert{\Sigma}\right\vert$ is finite in the definition), i.e., a regular language is any set $S$

$$ \left\vert{S}\right\vert \le \left\vert{\infty}\right\vert, {S} \in \Sigma \\ \left\vert{\Sigma}\right\vert \lt \left\vert{\infty}\right\vert $$

I think this is correct because the union, concatenation or Kleene star of a singleton that is part of a finite set or the empty set must be also part of that set, even when operated on recursively.

It's been a fair while since I did any maths, and even longer since I've touched set theory. Have I completely misread Wikipedia's definition? If so, how? If I haven't how is a regular language different from my definition?

Answer 1

Regular languages over a finite alphabet are always countable: indeed, $\Sigma^*$ is countable. However, not every subset of $\Sigma^*$ is regular. This is because the set of regular languages is only finitely additive rather than $\sigma$-additive. That means that if $A_1,\ldots,A_\ell$ are regular then so is $A_1 \cup \cdots \cup A_\ell$, but the same isn't true for an infinite sequence. Indeed, every subset of $\Sigma^*$ can be written as an infinite sum of singletons (sets of size $1$), which are regular, but not all subsets of $\Sigma^*$ are regular. For example, the following subset of $\{0,1\}^*$ isn't: $\{ 0^n 1^n : n \geq 0 \}$.

You define a regular language as one which has a finite number of unique elements. Unfortunately, you don't define what these unique elements are, so your definition is vague at best. Regular languages have other definitions than the one given by Wikipedia - for example, they are the languages accepted by deterministic finite automata, by non-deterministic finite automata, and by Turing machines running in time $o(n\log n)$. Each of these has a finite number of states, which might correspond to your unique elements. A third approach defines a regular language as one having finitely many Myhill-Nerode equivalence classes (two words $x,y \in \Sigma^*$ are equivalent with respect to a language $L$ if for all $z \in \Sigma^*$, $xz \in L$ iff $yz \in L$).

Here is a Wikipedia-like definition of the regular languages (both definitions are the same for finite $\Sigma$). It is the smallest collection of languages which:

1. Contains all singletons $\{a\}$ for $a \in \Sigma$.
2. Closed under finite unions and intersections, under complementation, under concatenation, and under Kleene star.

Every regular language has a "proof" of its being regular which comes from applying the operations above. In the case of the Wikipedia definition, this proof is a regular expression, which is why they chose their particular definition. For example, $0^*1^* + 1^*0^*$, the language of "monotone" sequences over $\Sigma = \{0,1\}$, can be derived as follows from Wikipedia's rules:

1. $0$ is regular (singleton axiom).
2. $0^*$ is regular (Kleene star applied to (1)).
3. $1$ is regular (singleton axiom).
4. $1^*$ is regular (Kleene star applied to (3)).
5. $0^*1^*$ is regular (concatenation of (2) and (4)).
6. $1^*0^*$ is regular (concatenation of (4) and (2)).
7. $0^*1^* + 1^*0^*$ is regular (union of (5) and (6)).

My rules are more permissive: they allow complementation and intersection. You can try to prove that both definitions are equivalent - this is quite difficult from these definitions, but becomes much easier using either DFAs (deterministic finite automata) or Myhill-Nerode relations.