I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ One grammar just lists each string as a production for the start symbol. There are clearly an infinite number of grammars that generate the given strings, so without any other criteria on the grammar, this problem just has no possible answer. $\endgroup$– vonbrandJul 23, 2015 at 2:34
-
$\begingroup$ This question falls a bit short (cf vonbrand) but it's also way too broad; learning grammars in an entire research subfield! $\endgroup$– Raphael ♦Jul 24, 2015 at 6:15
-
$\begingroup$ It wasn't obvious to me that having only positive examples is not enough to induce a grammar. The answer by @D.W. made that clear. While I understand that grammar induction itself is a sizable field of research, wouldn't this question and the accepted answer below help someone else like me overcome the same misconception? $\endgroup$– Prashanth EllinaJul 25, 2015 at 15:44
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
If you have only positive examples (strings that are in the language), in principle, no, you cannot infer the grammar. For all you can tell, the language might be $\Sigma^*$: no matter how many example strings you have, you'll never be able to rule that out as the language.
However, if you have a little more information, there are known solutions. You can take a look at Angluin's algorithm. If you need a software implementation, take a look at LearnLib. See also Wikipedia's page on grammar induction for other approaches.
Another approach is to try to find the smallest context-free grammar that can generate every string in your set of examples, and nothing else. Finding the absolute smallest CFG is probably hard, but there are known heuristics that tend to give a good solution in practice. I'd recommend the Sequitur algorithm, if you need something in practice and have only positive examples. This gives up generalization -- there might be an even simpler/smaller CFG that can generate every one of your example strings as well as some others -- but for some applications it works reasonably well in practice.
-
$\begingroup$ This is a good answer to a rather bad question. Do you see a good edit that would make the question worth keeping? $\endgroup$– Raphael ♦Jul 24, 2015 at 6:17