Experiments and comparison of inference methods of regular grammars

摘要

Some common algorithms for regular grammatical inference with different regular grammars have been tested in order to clarify how they can consider those languages. The methods of so-called successor, canonical derivative, k-tails, tail-clustering, and skeleton have been examined experimentally. The two last-mentioned methods were shown to be the best and the most general when inferring regular grammars that were close to minimal initial grammars used to generate input strings for the inference process. It was noticed that the quality of the inferred grammars depends to a considerable extent on the properties of input strings.