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.

  • $\begingroup$ What you want to do is learn an (infinite?) language after having seen a finite sample, with or without (too much) overgeneralisation. That is a hard task. What have you read about this? (If you only want a grammar for exactly that finite set, the answer is trivial.) $\endgroup$
    – Raphael
    Commented Jan 28, 2013 at 10:32
  • 2
    $\begingroup$ So what you're looking for is a (simple) algorithm that performs context-free grammatical inference (CFGI). You can try searching those keywords on google scholar or something else. A quick search returned this review chapter from a Ph.D. thesis. Maybe you'll find what you're looking for in there, or at least pointers to steer your search. $\endgroup$
    – Khaur
    Commented Jan 28, 2013 at 11:15
  • $\begingroup$ Given $w_1,\ldots,w_n$, how about the grammar with the rules $S \to w_i$? $\endgroup$ Commented Jan 28, 2013 at 14:38
  • $\begingroup$ @YuvalFilmus That would be a simple way to build a grammar, but the grammar wouldn't be very natural, would it? $\endgroup$
    – Khaur
    Commented Jan 28, 2013 at 14:43
  • $\begingroup$ Thank you for the pointers. "Learning" and "inference" seem to be the right terms. To clarify, I am not interested in this topic in general, but just in this particular algorithm that I remember to be strikingly simple (in the striking contrast with the papers on grammatical inference). I thought it might be well-known, but maybe the algorithm is applicable only in some narrow case or has some other restriction. Sorry for being so vague, I'll try to remember more details. $\endgroup$
    – nikita
    Commented Jan 28, 2013 at 15:31

2 Answers 2


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).

  • $\begingroup$ Welcome to cs.stackexchange! It is generally advised to add some description/details in your answer instead of just a link - links could break. It would be nice if you could add some overview of what the algorithm does and how. That will substantially improve your answer. $\endgroup$
    – Paresh
    Commented Jan 29, 2013 at 8:17

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 https://stackoverflow.com/q/15512918/781723 and the surrounding literature.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.