Regular Pumping Lemma

Let be a Formal Language We say satisfies the regular pumping lemma with pumping number if for every word with there are words such tat , , and for all we have .

Theorem

For every Regular Formal Language , there is a number st satisfies regular pumping lemma with pumping number .

Proof

is generated by some Deterministic Automata .

We claim .

Take any with . Let where and .

By Pigeon Hole Principle, there are some st (ie we returned to the same state)

Now label , and and prove by induction that is still accepted (starting from !!!)

(SHOULD BE MORE CAREFUL WITH INDICES)