Which of the following is TRUE about the Pumping Lemma for regular language?

Answer: It applies to all regular languages.

Pumping Lemma (for regular languages): For every regular language L there exists an integer p (called the pumping length) such that any string s in L with |s| >= p can be decomposed as s = xyz with |xy| <= p, |y| >= 1, and for all i >= 0 the string xy^i z is also in L.

• Why the statement is true: the lemma is proved from the structure of deterministic finite automata; every regular language has some finite-state machine, which yields a pumping length.

• Finite regular languages: the lemma still 'applies' because if no string has length >= p the condition is vacuously true.

• Important remark: the pumping lemma provides a necessary condition for regularity but not a sufficient one. Satisfying the lemma does not automatically guarantee a language is regular.

How to use the lemma to prove non-regularity:

1. Assume the language is regular and let p be the pumping length guaranteed by the lemma.

2. Choose a specific string s in the language with |s| >= p (usually crafted to force any possible decomposition to fail).

3. Consider all decompositions s = xyz that satisfy |xy| <= p and |y| >= 1, and show there exists some i (often i = 0 or i = 2) for which xy^i z is not in the language.

4. This contradiction shows the language cannot be regular.