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
minimal languages that cover grammar productions
reference request;big picture;application of theory;grammars;minimization