Pumping lemma
- A Theory used to prove that a given languae is not Regular.
- It can't be used to prove Regular
If A is a RL, then A has a Pumping Length P such that string S where |S|>=P may be divided into 3 parts S = xyz such that the following conditions must be true.
- xy^iz is an element of A for i>0
- |y| >0
- |xy| >=P
Let's prove a^nb^n is not Regular with Punping Lemma.
A = a^nb^n
If A is a Regular Language, then A has a length P, where |S| >=P. S can be divided xyz.
Let S = a^pb^p and P =7.
We can divide into 3 cases
- y is part of the sequence of a.
- In this case, if y increases # of a and b are not same. => contdition false.
- y is part of the sequence of b.
- In this case, if y increases # of a and b are not same. => condition false.
- y includes a section and b section. ex) y = aabb
- In this case, if y increases, the pattern of the word is differ from the grammar(a^nb^n). => condition false.
All cases can't satisfy the condition, A is not Regular.
gg