First of all, that should be
(I would detract at least half a point for that).
Okay. The general idea is as follows. We want to check if a language is regular, ie if there exists a (deterministic) finite automaton that accepts L (ie all words in L and only the words in L).
Let's assume L is regular, then there is such an automaton A. Let's assume it's minimal (the minimal automaton for a given language is unique) and has n states.
Then in order for it to accept words with more than n letters, it has to visit some states multiple times (this is called the pigeon hole principle). So there must be a loop in the automaton.
That also means that we can this loop an arbitrary number of times, so our words in L(A) keep getting longer and longer.
The pumping lemma now states:
L is regular iff
there exists some n >=1 such that
for each word w in L with length of at least n,
there exists a breakdown (Zerlegung) of the word in three parts x, y and z (w=xyz)
such that the following conditions are true at the same time:
1) y is not empty
2) length(xy)<=n
3) for each i>=0, x(y^i)z is in L.
Plainly speaking: y is the part that would be looped in our run on the automaton A. We should also be able to not loop this at all and still be in the language.
So we now take some word of length at least n. For that, we know that we are looping some portion of the run.
The task helpfully provides the word 0^n10^n, which is also what I would have taken.
Now, we need to find a breakdown of the word such that the conditions 1 and 2 hold.
In particular, length(xy) is at most n, but xyz it also spans the whole word. So we have the following case:
x=0^k, y=0^j such that k+j<=n and j!=0 (the latter, because the length of y is not empty as per 1)
Then z = 0^m10^n (the remainder of the word). Note that m is 0 iff k+j=n.
Now, consider what happens if we set i=2 and look at x(y^i)z. This becomes
x(y^2)z
=0^k(0^(2*j))0^m10^n
=0^(n+j)10^n which is not in the language.
As an alternative, we could also look at i=0. Then we get 0^(n-j)10^n which is also not in the language.
Now we have done a proof by contradiction. We assumed L was regular. Then the conditions 1 to 3 must hold true. However, we broke condition 3. Thus, our premise is wrong and L is non-regular.
Basically, in order to prove a language L is non-regular:
* you find a word in L which has at least size n
* you consider how a breakdown with conditions 1 and 2 would look like
* you consider what happens if you set the i in condition 3 to some arbitrary values which are not equal to 1. Usually, 0 or 2 will do the trick.
Author
Topic: Can't Think of a Breaking Bad Pun For the Title: Let's Do Some Math! (Read 56947 times)