2
$\begingroup$

Let $L$ be a language. $w \in\ L$ , and $w$ could be broken in $xyz$.

Then if $L$ is regular, there exists a pumping length $p$ such that:

  1. $\vert y\vert>0$
  2. $\vert xy\vert \leq p$
  3. $\forall i \geq 0,\ xy^i z\ \in L$

I understand that this lemma is

  • based on pigeon hole principle
  • we use it to prove that a language is not regular by contradiction.

For condition (1), I understand that the string we are pumping should be $\geq 1$.

But I don't understand the significance of condition (2).

Why should the length of $xy$ be equal to or smaller than $p$ . Won't it work otherwise?

$\endgroup$
0

1 Answer 1

5
$\begingroup$

$p$ is the number of states in the automaton. As you say, the pumping lemma is about the pigeonhole principle. Suppose that $q$ is the first state that's repeated when you read input $w$. Then $x$ is the string that you read before you reach $q$ for the first time, and $y$ is the string you read between the first and second visits to $q$. Since there are only $p$ states including the start state, you must repeat a state after doing at most $p$ transitions, i.e., reading a string of length at most $p$. So the condition $|xy|\leq p$ comes from the proof.

In reality, when an automaton reads a particular string $w$, there might be many times when it returns to a state that has already been visited. If you take $w\in L$ any split $w=xyz$ with $|y|\geq 1$, such that the automaton is in the same state at the beginning and end of $y$ then $xy^iz$ will be in $L$ for all $i$, regardless of how long $xy$ is.

$\endgroup$
3
  • $\begingroup$ Thanks. Now it makes sense. Before repeating we have to visit at most p states. $\endgroup$
    – rsonx
    Mar 31, 2019 at 4:07
  • $\begingroup$ Does pumping lemma works for multi-loop automata? Lets say there are more than one loop. $\endgroup$
    – rsonx
    Mar 31, 2019 at 4:10
  • $\begingroup$ @Revolver Yes, it works for any automaton. The pigeonhole principle guarantees that there's at least one loop. More loops could only makes things "easier", but we can't exploit that, because we don't know for sure that any more loops exist. We just have to work with the one we can guarantee. $\endgroup$ Mar 31, 2019 at 8:41

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