Is there a non-reg lang L such that you CANNOT prove L non-reg via pumping and reductions?
There are many pumping theorems (one of which is iff so you could use it on all non-reg but you wouldn't want to-- its in the paper pointed to later). I'll pick the most powerful Pumping Lemma that I can imagine teaching a class of ugrads:
If L is regular then there exists n0 such that for all w∈ L, |w| ≥ n0 and all prefixes x' of w
with |w|-|x'| ≥ n0 there exists x,y,z such that
|x| ≤ n0
y is nonempty
w=x'xyz
for all i ≥ 0 x'xyiz ∈ L
If this is all we could use then the question is silly: just take
{ w : number of a's NOT EQUAL number of b's }
which is not regular but satisfies the pumping lemma above. SO I also allow closure properties. I define (and this differs from my last post--- I thank my readers, some of whom emailed me, for help in clarifying the question)
A ≤ B
if there exists a function f such that if f(A) = B then A regular implies B regular
(e.g., f(A) = A ∩ a*b* )
(CORRECTION: Should be B Regular --> A regular. Paul Beame pointed this out in the comments.)
(CORRECTION- My definition does not work. I need something like what one of the commenters suggested and what I had in a prior blog post. Let CL be a closure function if for all A, if A is
regular than CL(A) is regular. Like f(A) = A cap a*b*. Want a^nb^n \le numb a's = numb b's
via f(A) = A cap a*b*. So want A \le B if there is a closure function f with f(B) = A. )
A set B is Easily proven non-reg if either
a) B does not satisfy the pumping lemma, or
b) there exists a set A that does not satisfy the pumping lemma such that A ≤ B.
OPEN QUESTION (at least open for me, I am hoping someone out there knows the answer)
Is there a language that is not regular but NOT easily proven non-reg?
OPEN QUESTION (at least open for me, I am hoping someone out there knows the answer)
Is there a language that is not regular but NOT easily proven non-reg?
Ehrenfeucht, Parikh, Rozenberg in a paper Pumping Lemmas for Regular Sets (I could not find the official version but I found the Tech Report on line: here. Ask your grandparents what a Tech report is. Or see this post: here) from Lance about Tech Reports) proved an iff pumping lemma. They gave as their motivating example an uncountable number of languages that could not be proved non-regular even with a rather fancy pumping lemma. But there lang CAN be easily proven non-reg. I describe that here. (This is the same paper that proves and iff Pumping Lemma. It uses Ramsey Theory so I should like it. Oh well.)
SO, I looked around for candidates for non-reg languages that could not be easily proven non-regular. The following were candidates but I unfortunately(?) found ways to prove them non-regular using PL and Closure (I found the ways by asking some bright undergraduates, to give credit- Aaron George did these.)
{ aibj : i and j are relatively prime }
{xxRw : x,w nonempty } where R is Reverse.
I leave it to the reader to prove these are easily proven non-regular.
To re-iterate my original question: Find a non-reg lang that is not easily proven non-reg.
Side Question- my definition of reduction seems a bit odd in that I am defining it the way I want it to turn out. Could poly-Turing reduction have been defined as A ≤ B iff if A is in P then B is in P? Is that equivalent to the usual definition? Can I get a more natural definition for my regular reductions?
I imagine a pretty reasonable way to define reductions in this world is to say A <= B if A can be formed by regular expressions that use B as a basic set (for example A = B*{0,11}).
ReplyDeleteFor your question about poly-time Turing reductions, it's pretty clear that these two definitions are not equivalent as one lets the halting problem be reduced to any computable language outside of P whereas the other does not. If your question was meant to be "just considering pairs of languages in NP", I don't actually know if given P different from NP that there is an L in NP\P where NP doesn't poly-time Turing reduce to L (maybe Ladner's theorem or some extension shows this?), but certainly if SAT isn't in QuasiP, then SAT can't be poly-time Turing reduced to anything in QuasiP, and this would again give us a discrepancy in these two definitions.
First note that the direction for your reduction function f is somewhat the opposite of the usual notion which preserves easiness in the other direction. (If B is easy then A is easy.) I will use the direction you gave despite this grumbling...
ReplyDeleteHowever, it is easy to resolve your question because there is a fundamental problem with your definition of reduction that makes the answer to your OPEN QUESTION a trivial NO. Let B* be a non-regular problem for which (a) does not hold. That is, the non-regularity of B* does not follow by the pumping lemma (i.e., it satisfies the pumping lemma). Let A* be any other language that is not regular that does follow by the pumping lemma (it doesn't satisfy the pumping lemma).
Define function f on languages by:
f(A*)=B* and if A != A* then f(A)=A.
Clearly f preserves regularity because it satisfies an EVEN STRONGER condition: A is regular iff f(A) is regular.
Therefore by your definition A* <= B*. It follows that B* satisfies case (b) of your definition of being easily proven non-regular.
I don't like the pumping lemma because it hides the reasoning behind a complicated lemma statement. For that reason, I avoided teaching it many times. The strategy I use when I want to show to the students that some language is not regular is the following. I define that two prefixes A and B are distinguishable if there is a string W such that AW is in the language and BW is not or vice versa. If I can show there are arbitrarily large sets of pairwise distinguishable prefixes, then the language is not regular. (The reason being that multiple prefixes would lead to the same state of the DFA, and therefore either both would accept the suffix W or reject it.) I've never thought of it, but I'd be surprised if there are nonregular languages that cannot be showed nonregular by this approach.
ReplyDeleteThis is precisely Myhill-Nerod theorem, right?
DeleteI have no idea. I would not believe I was the first person to think of it though.
DeleteI'll think about more reasonable examples, but clearly you can hook the non-regularity of A to some hard to "decode" (or even undecidable) functions; e.g.:
ReplyDeletee.g. A = { a^n | the n-th Turing machine halts after 2^n steps }
I think it's quite hard to (formally) prove that it's not regular using the pumping lemma or other standard tools because it highly depends on the encoding.
In other words you can "play" with the fact that unary regular languages are a union of semilinear sets (the set of exponents of the regular unary langauge is an union of semilinear sets); and if it's difficult to prove that a set B is not semilinear then it's hard to prove that the corresponding A = { a^n | n \in B} is not regular.
Another silly example would be to let A be a non-regular language if the Riemann hypothesis holds, and let it be empty otherwise.
DeleteLet me be the defender of the pumping lemma. Here’s a good generalization: If L is regular then there is an n s.t. for x in L, if x=abc with |b|=n there is a uvw with |v|>0 such that auv^iwc is in L for all i.
ReplyDeleteWith the definition every language given by Bill can be pumped directly--no need for closure properties. It’s very hard to come up with a non-regular language that fulfills this pumping lemma.
I might be wrong, but there seems to be an one easy way to defeat the pumping lemma as follows. For any language L over {0,1}, take the language L' that has the same words as L, except that it can contain an arbitrary number of 2's anywhere in the word, and at least one between any two original numbers, the beginning and the end. For example, 101 can be converted to 2122202222122. Whenever one tries to pump a word with these properties, it's possible that always the 2's get pumped. If you try to pump a word that doesn't have enough 2's, you might end up with one that also doesn't have enough 2's. Of course, if you don't like 2's, you can work with extended binary, and convert an original 0 to 00, 1 to 10 and 2 to 11.
ReplyDeleteA pumping length p', in L' corresponds to a pumping length p'/2 in L; indeed you can pick a string w' = x'y'z' with |w'| >|p'| in which there is only one 2 between two {0,1} symbols.
DeleteSuppose that p' is even, then the substring y' than can be pumped must be of the form:
1) y' = 2 (0|1) 2 ... 2 (0|1) or
2) y' = (0|1) 2 ... 2 (0|1) 2 or
In every case pumping it and proving that the resulting string (which is still in the form with exactly one interleaving 2 between the 0s and 1s) falls out of L' should not be more difficult than proving it in the original L.
You seem to use that in the pumped string we also have exactly one 2 in every gap, but this is not required. In fact, it's possible that we only pump a single 2.
DeleteI said that, given the pumping length p', we can pick as "reference" string w' = x'y'z' with |w'| >|p'| as string w' in which we have exactly one 2 between every 0,1 symbols. In this case, if we have a pumping string of only one 2 (i.e. y' = "2") we can pump zero times and we get a string out of the language ("... and at least one between any two original numbers ..." from your answer). So we must have at least one 0,1 in y' (and at least one 2 at the beginning or at the end). But in this case we should be able to apply the pumping lemma easily in the same manner as we apply it on the original L.
DeleteYou're right, I haven't realized that we can pump zero times!
Delete