January 30th, 2012
Identifying Nonregular Languages
We can use something called a Pumping Lemma to help us prove that certain
languages are nonregular. When considering DFAs, we see that they have a bounded
amount of memory. We also note that DFAs cannot accept languages where it is
necessary to count arbitrary numbers.
Claim : The language L = fa b jn ▯ 0g over ▯ = fa;bg is not regular.
Intuition : Any DFA would have to "count the number of a’s and match it with
the number of b’s.
Proof : Suppose there is a DFA M = (Q;▯;▯;q ;F) 0hat accepts L. Consider the
states ▯ (q0;a ) for i = 0;1;2;:::
Since there is an unbounded number of i’s, but Q is