2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Note that there's no such thing as "considered regular": regularity is a matter of fact, not opinion. $\endgroup$ – David Richerby Mar 12 at 14:22
3
$\begingroup$

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".)

$\endgroup$
  • 1
    $\begingroup$ You don't get to break up $w$ into three parts. You have to rule out every possible breaking of $w$ into three parts. $\endgroup$ – Yuval Filmus Mar 12 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.