whether or not L (G) = .
* Later we will make precise what the term “algorithm” means. For the moment, think of it as a method
for which one can write a computer program.
4.3 Identifying Nonregular Languages
Regular languages can be infinite, as most of our examples have demonstrated.
The fact that regular languages are associated with automata that have finite
memory, however, imposes some limits on the structure of a regular language.
Some narrow restrictions must be obeyed if regularity is to hold. Intuition tells
us that a language is regular only if, in processing any string, the information
that has to be remembered at any stage is strictly limited. This is true, but has to
be shown precisely to be used in any meaningful way. There are several ways in
which this can be done.
Using the Pigeonhole Principle
The term “pigeonhole principle” is used by mathematicians to refer to the
following simple observation. If we put n objects into m boxes (pigeonholes),
and if n > m, then at least one box must have more than one item in it. This is
such an obvious fact that it is surprising how many deep results can be obtained
from it.
Example 4.6
Is the language L ={a n b n : n ≥ 0} regular? The answer is no, as we show using a
proof by contradiction.
Suppose L is regular. Then some dfa M = (Q, {a, b},δ, q 0 , F) exists for it.
Now look at δ* (q 0 ,a i ) for i = 1, 2, 3,…. Since there are an unlimited number of
i’s, but only a finite number of states in M, the pigeonhole principle tells us that
there must be some state, say q, such that
and