Learning Context Free Grammars by Using SAT Solvers

In this paper, we propose a novel approach for learning context free grammars (CFGs) from positive and negative samples by solving a Boolean satisfiability problem (SAT). We encode the set of samples, together with limits on the sizes of rule sets to be synthesized as a Boolean expression. An assignment satisfying the Boolean expression contains a minimal set of rules that derives all positive samples and no negative samples. A feature of this approach is that we can synthesize the minimal set of rules in Chomsky normal form. The other feature is that our learning method reflects any improvements of SAT solvers. We present experimental results on learning CFGs for fundamental context free languages, including a set of strings composed of the equal numbers of a's and b's and the set of strings over {a, b}* not of the form ww.