1
$\begingroup$

I found this on Wikipedia and I'm confused by the parenthesis in the notation not that it doesn't make sense to me but is there a more natural human version? And im generally confused about all the different notations surrounding logic and quantifier.

$(\forall L \subseteq \Sigma^*)(regular(l)\Rightarrow((\exists p\geq1)((\forall w\in L)$ $((|w|\geq p)\Rightarrow((\exists x,y,z\in \Sigma^\ast )(w = xyz \land(|y|\geq 1\land|xy|\leq p \land(\forall n\geq 0)(xy^nz\in L))))))))$

$\endgroup$

1 Answer 1

2
$\begingroup$

I agree that the way the lemma is written is confusing, a more friendly way to write the lemma is as follows (I have added an intuitive explanation for the conditions appearing in the lemma, hoping that it is more human readable now):

The Pumping Lemma: for every regular language $L\subseteq \Sigma^*$, there is a positive pumping constant $p$ such that for every word $w\in L$ with $|w|\geq p$ (that is, for every long enough word in the language $L$ ), the following holds. There exists a partition of $w$ into three words over $\Sigma$, $w = xyz$, such that:

  1. $|xy|\leq p$ (that is, $y$ lies in the prefix of length $p$ of $w$).

  2. $|y| > 0$ (that is, $y$ is nonempty).

  3. $xy^iz\in L$, for every $i\geq 0$ (that is, if you take the word $w$ and pump the infix $y$ in $w$, $i$ times, the word $w$ remains in the language $L$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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