<p>this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site <a href="https://cs.stackexchange.com/">cs.se</a> <em>(now with more questions than this one!)</em> 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.</p>

<blockquote>
  <p>what is the smallest language that "covers" all the grammar production rules/symbols?</p>
</blockquote>

<p>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 &amp; nondeterminism. looking for eg ref(s), thms, complexity, theory, connections, applications, insight etc.</p>

<p>[1] <a href="https://cs.stackexchange.com/questions/28264/generating-a-set-of-minimal-length-strings-that-together-invoke-every-producti">Generating a set of minimal-length strings that, together, invoke every production of a context free language</a> / <a href="https://cs.stackexchange.com/users/755/d-w">D.W.</a>, cs.se<br>
[2] <a href="https://cs.stackexchange.com/questions/28282/transition-coverage-for-a-dfa">Transition coverage for a DFA</a> / <a href="https://cs.stackexchange.com/users/16612/patrick-collins">Patrick Collins</a>, cs.se</p>

CC BY-SA 3.0
2014-07-19T15:32:30.330Z
eg on [1] [babou](http://cs.stackexchange.com/users/8321/babou) found [this paper](http://www.sciencedirect.com/science/article/pii/0020019077900023) 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.
vzn
CC BY-SA 3.0
2014-07-19T22:53:14.403Z
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.
babou
<reference-request><big-picture><application-of-theory><grammars><minimization>
minimal languages that "cover" grammar productions
vzn
# minimal languages that "cover" grammar productions

(Asked by: username_0 on 2014-07-18)

this question is based on generalizing two somewhat similar questions that recently appeared on the "sister" beta site [cs.se](https://cs.stackexchange.com/) *(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](https://cs.stackexchange.com/questions/28264/generating-a-set-of-minimal-length-strings-that-together-invoke-every-producti) / [D.W.](https://cs.stackexchange.com/users/755/d-w), cs.se  
[2] [Transition coverage for a DFA](https://cs.stackexchange.com/questions/28282/transition-coverage-for-a-dfa) / [Patrick Collins](https://cs.stackexchange.com/users/16612/patrick-collins), cs.se

**Tags:** reference-request, big-picture, application-of-theory, grammars, minimization
> **Comments:**
> **username_0**: eg on [1] [babou](http://cs.stackexchange.com/users/8321/babou) found [this paper](http://www.sciencedirect.com/science/article/pii/0020019077900023) 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.  
> **username_1**: 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.  

---

## 0 answers

