# 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

1
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

## 1 Answer

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

-

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. – Paresh Jan 29 at 8:17
This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post - you can always comment on your own posts, and once you have sufficient reputation you will be able to comment on any post. – AJed Jan 29 at 14:15
Yes, this is exactly it! Thank you. – nikita Jan 29 at 18:32
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 2, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9393959641456604, "perplexity_flag": "middle"}