Problem Detail: From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around? If given n strings of m length, it should be possible to make a grammar that will generate those strings, and just those strings. Is there a known method for doing this? Ideally a technique name I can research. Alternatively, how would I go about doing a literature search to find such a method?
Asked By : Gustav Bertram
Answered By : D.W.
This falls within the general topic of “grammar induction”; searching on that phrase will turn up tons of literature. See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar_induction, http://cstheory.stackexchange.com/q/27347/5038. For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, Smallest DFA that accepts given strings and rejects other given strings, Are there improvements on Dana Angluin's algorithm for learning regular sets, and http://cstheory.stackexchange.com/q/1854/5038.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/53279
