3
$\begingroup$

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site cs.se (now with more questions than this one!) and which seems theoretically significant yet maybe not studied much in the literature. consider a grammar as a set of production rules, terminal and nonterminal symbols.

what is the smallest language that "covers" all the grammar production rules/symbols?

by "covering" what is meant that every grammar production rule is invoked at least once in a derivation of the acceptance of the word, and including all the terminals. the smallest language is necessarily finite, ie a set of words/strings. the question arose (roughly) in the context of DFAs[2] and CFLs[1]. the problem becomes more complex in the case of CFLs, ambiguous languages & nondeterminism. looking for eg ref(s), thms, complexity, theory, connections, applications, insight etc.

[1] Generating a set of minimal-length strings that, together, invoke every production of a context free language / D.W., cs.se
[2] Transition coverage for a DFA / Patrick Collins, cs.se

Improve this question
$\endgroup$
2
  • $\begingroup$ eg on [1] babou found this paper by Knuth that generalizes Djikstras algorithm to CFLs that can be used to find a size-minimal terminal string that covers each/every production rule & leads to a straightfwd approach/algorithm (one at a time). however overall it seems this would turn out to be a greedy heuristic leading to local minima for some cases because some short terminal strings can cover multiple production rules and this incremental approach might not find them. $\endgroup$
    – vzn
    Jul 19, 2014 at 15:32
  • $\begingroup$ The problem is not the same for a DFA and for a NFA, if the paths covered are to be characterized by the strings they recognize. In the case of CF grammar, rule coverage is dependent on how you see ambiguity. Also, I assume that the size you consider for minimization is the sum of sizes of all strings in the cover. Also, that minimization was not what your reference [1] was asking. $\endgroup$
    – babou
    Jul 19, 2014 at 22:53

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.