I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense "natural" (e.g., the grammar doesn't produce all words in the alphabet). The algorithm is very simple, it has something like 3--4 rules for grammar transformation attempted on each new word. Any help in finding it would be appreciated.
|show 4 more comments|
I think you might be referring to Sequitur.
Edit It has been suggested by other commenters that I leave more information for posterity. Fair point.
Sequitur is an algorithm by Craig Neville-Manning and Ian Witten (of Managing Gigabytes fame). It's linear time in the size of the input sequences (although so is the memory usage), and satisfies the twin properties of parsimony (no redundant rules are derived) and utility (every rule is useful).
However, it can't (IIRC) discover arbitrary nesting structure. So a prototypical expression grammar, where an expression can contain an expression, is too much for it. But it will discover word boundaries in English text, and repeat regions in DNA. It's also useful for finding dictionaries for data compression (which is one of Witten's major research interests).
There are also many algorithms for DFA inference: given a set of words, infer a "natural" regular language containing all of those words. For instance, Angluin's L* is a classic algorithm in this space, but there are many others.
Of course, any regular language is also a context-free language, so this could be used for your purposes as well. Some of the algorithms are beautiful as well as useful in practice.
For more on this topic, you could look at http://stackoverflow.com/q/15512918/781723 and the surrounding literature.