3
$\begingroup$

I asked this earlier question about whether there is a pumping lemma for DCFLs and it looks like the answer is "no."

If the answer were "yes," an authoritative answer might have the form "yes there is, and it's called X and looks like Y." However, I'm concerned that there is no authoritative way for someone to answer the question as "no, such a thing does not exist," since a justification of this answer couldn't just be "I've never seen one" or "I don't think so."

Is there a way for someone to authoritatively give a "no" answer to my question? If not, what should I do?

Thanks!

$\endgroup$
2
$\begingroup$

I don't think so. "The best of my knowledge, no." or -- if you are confident -- "Such a result is not known." is sometimes the best answer possible, and should be posted as such. If you are wrong, somebody else will post the opposite and voting takes care of the problem, no harm done.

In some cases it may be possible to refer to standard/important books/publications that would list the result if it were known. If so, such references could yield the statement some weight.

$\endgroup$
  • 1
    $\begingroup$ I think this skirts the real issue: that it's not really possible to affirm or deny the existence of a "pumping lemma" for deterministic context free languages. What would disqualify any technique from being referred to as a "pumping lemma"? Surely if I invent a technique, I can call it what I want? $\endgroup$ – Patrick87 Apr 8 '13 at 18:14
  • $\begingroup$ @Patrick87 That's certainly true, but the "Pumping lemma" is quite closely tied to the act of going from some subword $v$ to $v^i$, as well as the general "game" structure of the property. Many English words have similarly been assigned TCS connotations, e.g. "reduction" or "diagonalisation". $\endgroup$ – Raphael♦ Apr 8 '13 at 19:13
0
$\begingroup$

Most likely, the symptom you're describing is one exhibited mostly by vague, ambiguous and hard-to-understand questions. In particular, I think it's probably pretty fair to characterize the linked question as "Not a real question" (certainly it seems well-intentioned, but the current wording is unproductive). The best answers address the question that likely ought to have been asked instead: how do you prove a language is deterministic context free? Clarification could have been given showing that the asker is aware of some proof methods, but finds them lacking in some respects.

Given that, the solution is probably to close such questions, reformulate them as appropriate and if possible, and only then reopen. Note that not all questions of the form "Does X exist (such that Y)?" suffer from the problem. For instance, we can prove that there are no NFAs whose minimal DFAs have more than 2^n states.

$\endgroup$
  • 2
    $\begingroup$ I don't quite agree. A learner may very well ask "Are there problems between P and NP-complete?", which should have a definite answer. Reasonable answers can be given, pointing out the openness of the problem. I agree, though, that the cited question is more problematic, but asking for a "standard" result for "new" classes is not unreasonable either. $\endgroup$ – Raphael♦ Apr 8 '13 at 18:07
  • 1
    $\begingroup$ Based on @Raphael's answer, I'd like to add one clarification to the above: my answer does not address questions which are answerable, but for which the answer may not be known (even by anybody). There's a difference between such questions and questions like "A duck is to a horse as a shoe is to what?"-type questions. The former may have "Nobody knows" as an acceptable answer; the latter are not good questions because it's hard to clearly distinguish correct from incorrect answers. $\endgroup$ – Patrick87 Apr 8 '13 at 18:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .