0
$\begingroup$

Pumping Lemma for Regular Languages

Pumping Lemma for Regular Languages: If $A$ is a regular language, then there is a number $p$ ( the pumping length ) where if $s$ is any string in $A$ of length atleast $p$, then $s$ may be divided into three pieces, $s=xy$, satisfying the following conditions:

  1. $for \ each \ i>=xy^iz∈A$,
  2. $|y|>0$, and
  3. $|xy|<=p$

When using pumping lemma to prove that a given language is "non regular, we do the following steps:

  1. Assume $L$ is regular, hence $L$ exhibits pumping lemma for regular langauges
  2. Since $L$ is regular, it will have $p$ and if we choose a string that is atleast as long as $p$
  3. Then that string will have decompositions satisfying all the three conditions of the lemma
  4. This is where we obtain a contradiction by showing that the string will fail to satisfy condition 1 of the lemma and hence our assumption is false and the language is not regular

My question is: Do we need to show that the string fails to satisfy condition 1 for one $i$ or all $i>=0$. I do understand that we need to show that string fails to satisfy for one $i$ but should the proof be able to extrapolate for any value of $i>=0$?

My understanding is that: In order to have a strong valid contradiction, we need to show that our string choice and pumping of the string fails for all values of $i$ according to condition 1

But when we say "for all values of $i>=0$", we know that for $i=1$, the pumped string does exist in the language( because we chose that string ), and sometimes it also exists in the langauge for $i=0$, so are these sort of exceptions?

$\endgroup$

1 Answer 1

2
$\begingroup$

Assuming the rest of the proof is formulated correctly, showing that every $xyz$ division fails to be pumped for at least a single value of $i$ is sufficient. To see this, let's inspect the formal definition of the pumping lemma, which states the following: (note the highlighted quantifiers)

For every regular language $L$, there exists an integer $p$ such that for every string $s \in L$ with $|s| \geq p$ there exists a way to partition $s$ into $xyz$ such that

  • $|xy| \leq p$
  • $|y| > 0$
  • $xy^iz \in L$ for every $i \geq 0$

We use the lemma in proofs by contradiction: hence, for all points where the lemma states that something must hold "for every" value of something, a single counter-example will be enough. Conversely, when the lemma states that something "exists", you must establish that no satisfactory value exists.

Usually, the way this is done is assuming a valid value of $p$ exists, then selecting a suitable string as we are allowed to, then examining all possible ways to partition the string and establish they fail at least one of the three conditions – usually ruling out the two first conditions, them being more trivial, and then showing each of the remaining possibilities violates the third condition for at least one value of $i$.

Intuition

Remember the pumping lemma is based on the behavior of the automaton recognizing the regular languages, a DFA. The intuition of the lemma is that for an automaton and its language $L$, a sufficiently long string must visit one of the states twice or more when being recognized. This means there is a loop in the string's "execution trace" on the DFA, and therefore a sequence of symbols $y$ that can be repeated to re-trace the loop arbitrarily many times, end in the same state, and continue from there to the accepting state.

Imagine the state that's the start and end of the loop. Since no many how times we pass through the loop, we end up in this state, it follows that we could also execute the loop zero times and cut out the portion of the string that caused our string to loop even once, and not change the acceptance of our string. For any string of a regular language, we could indeed do this – but if this results in a string that no longer belongs in our language, it proves that such a loop did not exist in the first place, confirming the language's non-regularity.

$\endgroup$
5
  • $\begingroup$ If that's the case why do people using $p!$ to prove that the following language is non regular: $0^n1^m$ where $n!=m$, here's an example: youtu.be/x2J5kaf6gjg?t=2860 .Instead, if we were just supposed to prove for atleast one 'i', then we could have just chose a string in the language asfollows $s=0^p1^{2p}$, then we if we can account for all decompositions as follows $x=0^a, \ y=0^b, \ z = 0^c1^{2p}$ where $a,c>=0$, $b>=1$ and $a+b+c=p$. Now, if we pump the decomposition once, we already fail the condition 1 of the lemma. Hence, this should have been enough, why do people use.. $\endgroup$ Jan 23, 2023 at 18:11
  • $\begingroup$ ..so complex solution to prove that the above given language is not regular $\endgroup$ Jan 23, 2023 at 18:11
  • $\begingroup$ Oh wait, do peope use the factorial decomposition for every decomposition whilst the solution that i gave will only work for the decomposition where 'y' has all 'p' zeroes? $\endgroup$ Jan 23, 2023 at 19:02
  • $\begingroup$ @PratikHadawale (rewrote earlier comment for more correctness & clarity) With $0^p1^{2p}$ you run into the problem that it's usually possible to select $y$ such that the amount of zeroes and ones don't match for any integer multiple. In your example, pumping the decomposition once doesn't fail the lemma: $xyyz = 0^a0^{2b}0^c1^{2p}$. Can you show that $a+2b+c = 2p$? You need to prove the number of the symbols eventually becomes equal. $\endgroup$
    – kviiri
    Jan 23, 2023 at 19:36
  • $\begingroup$ oh, that makes sense! I understand it now. Thank you for explaining so well! $\endgroup$ Jan 24, 2023 at 3:28

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.