Incremental learning of context free grammars based on bottom-up parsing and search |
| |
Authors: | Katsuhiko Nakamura [Author Vitae] Masashi Matsumoto [Author Vitae] |
| |
Affiliation: | a Department of Computers and Systems Engineering, Tokyo Denki University, Hatoyama-machi, Saitama-ken 350-0394, Japan b Distribution Systems Division, Hitachi Ltd., 6-23-15 Minami-Ohi, Shinagawa-ku, Tokyo 140-8570, Japan |
| |
Abstract: | This paper describes approaches for machine learning of context free grammars (CFGs) from positive and negative sample strings, which are implemented in Synapse system. The grammatical inference consists of a rule generation by “inductive CYK algorithm,” mechanisms for incremental learning, and search. Inductive CYK algorithm generates minimum production rules required for parsing positive samples, when the bottom-up parsing by CYK algorithm does not succeed. The incremental learning is used not only for synthesizing grammars by giving the system positive strings in the order of their length but also for learning grammars from other similar grammars. Synapse can synthesize fundamental ambiguous and unambiguous CFGs including nontrivial grammars such as the set of strings not of the form ww with w∈{a,b}+. |
| |
Keywords: | Incremental learning CYK algorithm Context free language Unambiguous grammar Chomsky normal form Synapse |
本文献已被 ScienceDirect 等数据库收录! |
|