A Polynomial Time Incremental Algorithm for Regular Grammar Inference

Date
1997-01-17
Authors
Parekh, Rajesh
Nichitiu, Codrin
Honavar, Vasant
Journal Title
Journal ISSN
Volume Title
Publisher
Altmetrics
Authors
Research Projects
Organizational Units
Computer Science
Organizational Unit
Journal Issue
Series
Abstract

We present an efficient incremental algorithm for learning regular grammars from labeled examples and membership queries. This algorithm is an extension of Angluin's {\em ID} procedure to an incremental framework. The learning algorithm is intermittently provided with labeled examples and has access to a knowledgeable teacher capable of answering membership queries. Based on the observed examples and the teacher's responses to membership queries, the learner constructs a deterministic finite automaton (DFA) with which all examples observed thus far are consistent. When additional examples are observed, the learner modifies this DFA suitably to encompass the information provided by the new examples. In the limit this algorithm is guaranteed to converge to a minimum state DFA corresponding to the target regular grammar. We prove the convergence of this algorithm in the limit and analyze its time and space complexities.

Description
Keywords
grammar inference, regular grammars, finite state automata, language learning, active learning, incremental algorithms, machine learning
Citation
DOI
Source
Collections