Confused about pumping lemma

Question

Here I have the method for pumping lemma to prove that a language $L$ is not regular:

1. Suppose to the contrary that L is regula, then $\exists$ DFA $A$, s.t. $L(A) = L$.
2. 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.
3. Choose a suitable $w \in L$, where $|w| \ge n$.
4. Find an $i$, such that $xy^iz \not\in L$. Since $xy^iz \in L(A)$, $L(A) \neq L$.
5. 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.

Answer 1

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?

Indeed. Although there are varying definitions for regularity (e.g., you may define the regular languages based on regular expressions), they are all equivalent. Hence, you only need to prove your language fails to satisfy one of the equivalent requirements to be regular. In the case of the pumping lemma, you argue on the basis of DFAs.

Second, how am I supposed to find "n" which is the number of states in A? Is this also known as the pumping length?

You are not supposed to find anything. In the classical variant of the pumping lemma, the number of states only appears explicitly in its proof. In the statement itself, there is only mention that such a number $n \in \mathbb{N}_0$ exists.

What is the proper way in which we are supposed to break up the string chosen string w >= n into 3 parts (xyz)?

The pumping lemma specifies what conditions should hold for $x$, $y$, and $z$. There are three of them. And, as $n$, when proving a language contradicts the lemma (to show it is not regular), you don't get to choose $xyz$; rather, you have to show your claim no matter what $x,y,z$ are (as long as they suffice the conditions from the lemma).

In your example, the word has prefix $a^n$, while one of the pumping lemma's requirements is $|xy| \le n$. Hence, there is no other option for $xy$ except for it to be a prefix of $a^n$, which is why you can extend this prefix to $a^{n + m|y|}$ for any $m \in \mathbb{N}_0$. (Remember: $y$ is the part that can be "pumped".)