Extending Incremental Learning of Context Free Grammars in Synapse

This paper describes recent improvements and extensions of Synapse system for learning of context free grammars (CFGs) from sample strings. The system uses rule generation based on bottom-up parsing, incremental learning, and search for rule sets. By the recent improvements, Synapse more rapidly synthesizes several nontrivial CFGs including an unambiguous grammar for the set of strings containing twice as many a’s as b’s and an ambiguous grammar for strings not of the form of ww. By employing a novel rule generation method called inverse derivation, the form of grammars is extended to definite clause grammars (DCGs) and broader classes of grammars such as graph and hypergraph grammars.