3 ms·
> we can "pump" a new string w' = xy^nz (for any n > 0) While this is certainly true, I would prefer to note that n ≥ 0. n > 0 is just a special case of that.
by thaumasiotes 5y ago
> we can "pump" a new string w' = xy^nz (for any n > 0)
While this is certainly true, I would prefer to note that n ≥ 0. n > 0 is just a special case of that.
(You can see clearly that 0 repetitions will always be valid by considering the proof of the pumping lemma: since a regular expression is recognized by a finite state machine, the only way to recognize a string of length exceeding the (finite!) number of states in the machine is to visit some states more than once, which means traveling around a cycle in the state graph. The 'pumpable substring' of the pumping lemma is a path through such a cycle, and repeating it zero times corresponds to traveling around the cycle zero times. The rest of the path is just as valid as always.)