3
$\begingroup$

I am looking for software/algorithm for the smallest context free grammar describing a finite set of words (and no other words).

For a single word I found sequitur

Related to this seems: given a CFG what is the shortest functionally equivalent CFG?

I would prefer the size to be measured by the CNF (for a precise estimate of the size).

To clarify I know the set can be described by a regular expression, this question is about the smallest CFG.

  • 4
    Since you want to describe *precisely* a finite set, you can never use recursion. Therefore, all you can do is look for (longest) common subsequences. In terms on non-terminals, surely the trivial (non-CNF) grammar just deriving all words from the starting symbol is minimal.2011-02-05

3 Answers 3