Limitations of Regular Languages

Since regular grammars are a special type of grammar, it is reasonable to assume that the set of regular languages is a subset of all possible languages. So what type of languages aren't regular?

First of all, we note one very important point:

Every finite language is regular

Any language is just a set of strings; a finite language is a set which contains a finite number of strings. We know this is regular, since if we have a finite language $\{w_1,\, w_2,\, ...,\, w_n\}$, we can rewrite it as the regular expression: w1 | w2 | ... | wn.

How do we form an infinite regular language? The union or concatenation of two finite languages will still be a finite language; thus, any infinite regular language must be formed from a regular expression which uses Kleene closure.

That means the regular expression which represents it must be of the form X(Y*)Z, where X, Y and Z are all regular expressions (possibly involving the use of Kleene-closure themselves). One implication of this is that every infinite regular language must have as a subset some set of words of the form $xy^iz$, for all $i\, \geq\, 0$, where $x$, $y$ and $z$ are strings which correspond to X, Y and Z respectively.

This conclusion is known as the Pumping Lemma for regular languages; ie:

if an infinite language $L$ is regular,
then there exist three strings $x$, $y$ and $z$ such that
$y \neq \varepsilon$ and $\{xy^iz\; \mid\; i\, \geq\, 0\}\; \subseteq\; L$