This paper describes inductive inference for synthesizing context free grammars from positive and negative sample strings,
implemented in
Synapse system. For effective inference of grammars, Synapse employs the following mechanisms.
| 1. |
A rule generating method called “inductive CYK algorithm,” which generates minimum production rules required for parsing positive
samples.
|
| 2. |
Incremental learning for adding newly generated rules to previously obtained rules.
|
Synapse can synthesize both ambiguous grammars and unambiguous grammars. Experimental results show recent improvement of Synapse
system to synthesize context free grammars.
Keywords incremental learning - inductive CYK algorithm - context - free language - unambiguous grammar - iterative deepening