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?

  • Kleene star gives you an infinite set for any $A \neq \emptyset$. – G. Bach Dec 8 '13 at 20:53
  • I don't think I'm disputing that anywhere @G.Bach. Assuming that $A$ is finite it gives you a countably infinite set rather than an uncountable one though. – Ben Dec 8 '13 at 20:55
  • I don't understand how a set can contain "a finite number of unique elements, though the set can be countably infinite" is what I meant to address. – G. Bach Dec 8 '13 at 21:23
  • As I say it's been a long time @G.Bach... but it seems that if $A = \{a\}$ then $A \cdot A$ performed recursively and infinitely will have one unique value, $a$, but infinite elements. It's countable because you know there's one unique value. – Ben Dec 8 '13 at 21:26
  • What do you mean by "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."? This is false. I think what you mean to say is that regular languages are closed under these operations: that applying any of them to regular sets always produces another regular set. – reinierpost Dec 9 '13 at 10:32

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.

  • Ok, wow... :-). To fixate on what seems to be the salient point I'm wrong because not all subsets of $\Sigma^*$ are regular. Doesn't this mean that Wikipedia is missing things? Because, an alphabet $\Sigma$ can be defined as a set of singletons $\Sigma = \{\{a_1\}, \{a_2\}, \{...\}, \{a_n\}\}$. The concatenation of each singleton is $\Sigma$ and the Kleene star of any concatenation under $\Sigma$ is a regular language? – Ben Dec 8 '13 at 21:19
  • The alphabet is not a set of singletons, rather it is a union of singletons $\Sigma = \{a_1,\ldots,a_n\}$. – Yuval Filmus Dec 8 '13 at 21:25
  • 2
    Wikipedia's definition is perfectly fine, it corresponds to regular expressions. When $|\Sigma| \geq 2$, not every subset of $\Sigma^*$ can be represented as a regular expression - indeed, only countably many subsets can be so represented, yet there are uncountably many subsets. – Yuval Filmus Dec 8 '13 at 21:32
  • @Yuval: thanks. If the alphabet $\Sigma$ is countably infinite, is $\Sigma$ not a regular language? Neither is $\Sigma^*$? Same answers when $\Sigma$ is uncountable? – Tim Jul 19 '14 at 3:52
  • @Tim Usually only finite $\Sigma$ are considered, but if you insist on infinite $\Sigma$ and the same syntax, then $\Sigma$ is not a regular language when $\Sigma$ is infinite. – Yuval Filmus Jul 20 '14 at 3:44

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.