# Construct a context-free grammar for a given set of words

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.

-
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.) – Raphael Jan 28 at 10:32
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. – Khaur Jan 28 at 11:15
Given $w_1,\ldots,w_n$, how about the grammar with the rules $S \to w_i$? – Yuval Filmus Jan 28 at 14:38
@YuvalFilmus That would be a simple way to build a grammar, but the grammar wouldn't be very natural, would it? – Khaur Jan 28 at 14:43
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. – nikita Jan 28 at 15:31
show 4 more comments