[LAC] Proving languages not to be regular

Are there non-regular languages?

The regular languages are those that can be recognized by finite automata; i.e. machines with finite memory.
Are there languages that are not regular?
Yes! One example:

So, how can we tell if a language is regular or not?
We use pumping lemma to tell!

Pumping lemma

Formal statement

Let L be a regular language, then there exists an integer n >= 1 depending only on L such that every string w in L of length at least n(n is called the “pumping length”) can be written as w = xyz, satisfying the following conditions:
1. |y| >= 1;
2. |xy| <= n
3. for all k >=0, x y^k z ∈ L

what does y mean?

y is the substring that can be pumped(removed or repeated any number of times, and the resulting string is always in L)
1. means the loop y to be pumped must be of length at least one.
2. means the loop must occur within the first n characters(|x| must be smaller than n)
Below is a formal expression of the pumping lemma:

Use of the lemma

The pumping lemma is often used to prove that a particular language is non-regular: a proof by contradiction will be used to proof that.

Proof of the pumping lemma

Above is a relationship between the states in pumping lemma.
Now, consider what happens if the automaton A receives the input x y^k z.
If k = 0; then the automaton goes from the start state q0(which is also p0) to pi on input x. Since pi is also pj, it must be that A goes from pi to the accepting state shown in image above. Thus, A accept xz.
If k > 0; then A goes from q0 to pi on input x, circle from pi to pi k times on input y^k, and then goes to the accepting state on input z. Thus, for any k>=0, x y^k z is also accepted by A.

Application/Example

Problem: Prove that L = {a^i b^i | i ≥ 0} is not regular.
Solution:

Example 2 (more challenging)

Problem: Prove that L = {0^n| n is a prefect square}.
Solution: let n be the constant in pumping-lemma.
And w = 0^n^2.
So there will be n^2 0’s.
When we write w = xyz, we can conduct that y is 1 to n 0’s
so if we make one loop ahead, xyyz will have (n^2)+1 to (n^2+n) 0’s
(because xyz is n^2 0’s and it adds a y)
However, Since the next perfect square after n^2 is(n+1)^2 =n^2 +2n+1, we know that the length of xyyz lies strictly between the consecutive perfect squares n2 and (n+1)2.
Thus, the length of xyyz cannot be a perfect square.