An Incremental Interactive Algorithm for Regular Grammar Inference

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

AAAI-96 Student Abstracts

Grammar inference, a problem with many applications in pattern recognition and language learning, is defined as follows: For an unknown grammar G, given a finite set of positive examples S+ that belong to L(G), and possibly a finite set of negative examples S-, infer a grammar G* equivalent to G. Different restrictions on S+ and S- and the interaction of the learner with the teacher or the environment give rise to different variants of this task. We present, an interactive incremental algorithm for inference of a finite state automaton (FSA) corresponding to an unknown regular grammar.