Here I have the method for pumping lemma to prove that a language $L$ is not regular:
- Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$.
- Let $n$ be the number of states in $A$. So, $\forall w ∈ L(A)$, if $|w| \ge n$, then $w = xyz$, where $x$, $y$, and $z$ as in Pumping Lemma.
- Choose a suitable $w \in L$, where $|w| \ge n$.
- Find an $i$, such that $xy^iz \not\in L$. Since $xy^iz \in L(A)$, $L(A) \neq L$.
- 4 contradicts 1, so 1 cannot be true and therefore $L$ cannot be regular
First of all, what are we trying to prove here in other words? That the language $L$ cannot be represented by a FSM, therefore cannot be considered "regular" because a regular language is only regular if it can be represented by a FSM?
Second, how am I supposed to find "$n$" which is the number of states in $A$? Is this also known as the pumping length?
What is the proper way in which we are supposed to break up the string chosen string $w \ge n$ into 3 parts ($xyz$)?
For example this teacher broke it up in this way:
$$\begin{align*} w &= a^{n}ba^{n+2}\\ i &= 2 \\ xy^2z &= a^{n+∣y∣}ba^{n+2} \end{align*}$$
How is the above equation equivalent? Why is he choosing $|y|$ and adding to to $n$?
And why would any of this prove that $L$ is not regular? I'm really confused about the whole thing.