Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
    
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 '13 at 10:32
2  
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 '13 at 11:15
    
Given $w_1,\ldots,w_n$, how about the grammar with the rules $S \to w_i$? –  Yuval Filmus Jan 28 '13 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 '13 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 '13 at 15:31

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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 '13 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 '13 at 14:15
    
Yes, this is exactly it! Thank you. –  nikita Jan 29 '13 at 18:32

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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