patternModerate
Is there a known method for constructing a grammar given a finite set of finite strings?
Viewed 0 times
finitemethodconstructinggrammarforknowntherestringsgivenset
Problem
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?
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?
Solution
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, https://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 https://cstheory.stackexchange.com/q/1854/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 https://cstheory.stackexchange.com/q/1854/5038.
Context
StackExchange Computer Science Q#53279, answer score: 12
Revisions (0)
No revisions yet.