Do we ever NEED the adv pumping lemma for Reg langs?

Recall the Pumping Lemma and the Advanced Pumping Lemma for Regular languages:

Pump. Lemma: If L is regular and infinite then there exists n such that

for all w∈ L , |w|≥ n, there exists x,y,z y≠ e, w=xyz, such that

for all i≥ 0 xyiz ∈ L.

Adv. Pump. Lemma: If L is regular and infinite then there exists n such that

for all w∈ L , |w|≥ n, there exists x,y,z y≠ e, AND |xz|≤ n,

w=xyz, such that for all i≥ 0 xyiz ∈ L.

The only difference is the bound on |xz|.



The question arises: Do you ever need the advanced pumping Lemma?

I will phrase this question rigorously.



One common way to prove that a lang is not regular is to use the pumping lemma.

Another common way is to use closure properties: To show that some L is not regular

show that L ∩ R where R is a known regular language, is not regular.

The proof that L ∩ R may be by the pumping lemma or by a further reduction.

Other closure properties may be used to.



If L is regular and f is a function from Σ to &Sigma*;, extend f to be on &Sigma*;

(f(xy)=f(x)f(y), then f(L) is regular. We denote this HOM for Homomorphism.



Given a language L in alphabet Σ we define a hierarchy over L.

Each level is a set of languages.



B(0) = {L} union EVERY regular language over Σ.



If L1, L2 are in B(i) then the following are in B(i+1):



L1 ∩ L2, L1 ∪ L2, COMP(L1), L1*, CONCAT(L1,L_2).



L1R = { w | w ∈ L1 } where wR is w written backwards.



For every f, a function from Σ to &Sigma*;, extend f to &Sigma*; via

f(xy)=f(x)f(y). Put f(L1) into B(i+1).



Let B(ω) = B(0) ∪ B(1) ∪ ...



RIGOROUS QUESTION 1: Is there a non regular language L such that

EVERY language in B(ω) satisfies the conclusion of the Pumping Lemma.



RIGOROUS QUESTION 2: Is there a non regular language L such that

EVERY language in B(ω) satisfies the conclusion of the Adv Pumping Lemma.



RIGOROUS QUESTION 3: Are there languages L such that, for all i, B(i) is a proper subset of B(i+1)?



RIGOROUS QUESTION 4: TRUE or FALSE: For all i there exists L such that the hierarchy is proper on the first

i levels but then collapses down to the ith level.



RIGOROUS QUESTION 5: TRUE or FALSE: For all i there exists L such that the first level where

a lang appears that DOES NOT satisfy the conclusion of Pump Lemma occurs on level i.



RIGOROUS QUESTION 6: TRUE or FALSE: For all i there exists L such that the first level where

a lang appears that DOES NOT satisfy the conclusion of Adv Pump Lemma occurs on level i.



A lang satisfying Q1 that could be proven non-reg with adv pumping lemma

(possibly with closure stuff) would be interesting in that it would be a case

where you NEED Adv Pumping Lemma.



A lang satisfying Q2 that could be proven non-reg with adv pumping lemma

(possibly with closure stuff) would be interesting in that it would lead to

other techniques to show langs not regular (such techniques may already

be known- the Myhill-Nerode Theorem may be one of them).