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
- 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).
- For every f, a function from Σ to &Sigma*;, extend f to &Sigma*; via
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).
What about Rigorous Question 0: Is there a language L that satisfies the pumping lemma but not the advanced pumping lemma?
ReplyDelete@Anonymous above me: L:= {a^ncc^*b^n | n \in N}. The role of y is only played by strings consisting of one or more c's. But the a and b part become arbitrarily long. I think this is also an answer for question 1.
ReplyDeleteWhich did Parikh do?
ReplyDeleteanon 1:01. Your lang does not answer Question 1. Intersect your lang
ReplyDeletewith a^* c b^* to get a^n c b^n which can be shown non-reg by the pumping lemma.
Anon 1:41. Parikh's theorem is on context free langs.
ad other techniques to show langs not regular - see the non-pumping lemma:
ReplyDeletehttp://www.csie.nctu.edu.tw/~ymhuang/formal_language/papers/the-end-of-pumping.pdf
http://cci.case.edu/cci/images/6/65/171-generalized-non-pumping.pdf
there are non-reg. languages which satisfy the conclusion of pumping lemma and not the non-pumping lemma and vice versa
The first paper you propose gives a very good candidate:
ReplyDelete{ x x^R w | x,w \in {0,1}^+ }
Pumping does not show it is non regular.
Does adv pumping?
Does closure propoerties- that is, if we start the B-hierarchy with this
lang, do we eventually get a lang that can be shown non-reg via pumping or adv pumping?
It is a fine question but ... why even bother with any version of the pumping lemma when the lower bound one gets from the easy direction of the Myhill-Nerode Theorem is (1) optimal and (usually) (2) more intuitive than and at least as easy to use as the pumping lemma?
ReplyDeleteRe Gasarch at 4:16 PM. I believe the following:
ReplyDeleteAdvanced pumping does not show that language to be non-regular. However, I believe that closure properties do. Specifically, I think you can intersect with the regular expression 01(11)*001(11)*01. That's a 0, an odd number of 1s, two 0s, an odd number of 1s, and another 1. I believe that such a word is in the language only if the odd number of 1s are the same, and then this language falls under the (weaker) pumping lemma.
I think the pumping lemma for regular languages is not very useful. Instead you can always start with the assumption that you have an NFA with n states that accepts the language. Then show that this leads to a contradiction via pumping an accepted word of length >= n in any consecutive block of n letters (since some state is repeated). Yeah, you're basically repeating the proof of the pumping lemma, now for a specific language. But this does not take more time than applying the pumping lemma itself. So the lemma is useless in the sense that it does not give a shorter proof.
ReplyDeleteMoreover, the students will be less bothered how to refute a lemma with this lots of quantifiers. (Actually, there is some use for this: the regular pumping lemma is a good exercise for applying the pumping lemma for context free languages).
Another good option is to use the Myhill-Nerode theorem. (as already Paul Beame pointed out)
I believe that your family B(omega) is more or less the subject of the paper:
ReplyDeleteGinsburg, Seymour; Goldstine, Jonathan Intersection-closed full AFL and the recursively enumerable languages. Information and Control 22 (1973), 201–231.
(They do not require closure under reversal in their definition; but otherwise it is basically the same.)
Lemma 3.1 of this paper almost gives what you are looking for: i.e., a language L such that every language in B(omega) satisfies the pumping lemma; except here the pumping lemma satisfied is slightly weaker than the usual one due to the words "almost all" that appear in the statement of the lemma.
Anyways, there's some interesting stuff there.