archives

Efficient Learning of Regular Languages Using Teacher-Supplied Positive Samples and Learner-Generated Queries


Home 

About 

Browse 

Search 

Register 

Subscriptions 

Deposit Papers 

Help
    

Parekh, Rajesh and Honavar, Vasant (1993) Efficient Learning of Regular Languages Using Teacher-Supplied Positive Samples and Learner-Generated Queries. Technical Report TR93-25, Department of Computer Science, Iowa State University.

Full text available as:Postscript
Adobe PDF

Abstract

EFFICIENT LEARNING OF REGULAR GRAMMARS
USING TEACHER-SUPPLIED POSITIVE SAMPLES
AND LEARNER GENERATED QUERIES
Rajesh G. Parekh & Vasant G. Honavar
Department of Computer Science
226 Atanasoff Hall
Iowa State University
Ames, IA 50011-1040
parekh@cs.iastate.edu, honavar@cs.iastate.edu
Technical Report 93-25
October 1992
We present a new algorithm for efficient learning of regular languages from
examples and queries. A reliable teacher who knows the unknown regular
grammar G (or is able to determine if  certain strings are accepted by the
grammar) will guide the learner in achieving the goal of inferring an
equivalent grammar $\mbox{G}^{*}$.  The teacher provides the learner with
a structurally complete set of positive examples belonging to the unknown
grammar G. Using this information the learner constructs a canonical
automaton which accepts exactly those examples.  The canonical automaton
defines a set of grammars which are ordered on a lattice to form the
hypothesis space. A bi-directional search algorithm  is used to
systematically search the lattice for the solution G*. While searching for
the solution, the learner interacts with the teacher by posing queries.
The teacher's responses enable the learner to eliminate one or more points
on the lattice which do not correspond to the correct solution. After
successive eliminations, when only one lattice element remains, the
process is terminated and that element is accepted as the solution G*.
The inferred grammar is proven to be equivalent to original grammar G.
___________________________________________________________________________
This research was partially supported by the Iowa State University College
of Liberal Arts and Sciences.
A preliminary version of this report was published in: Proceedings of
the Fifth UNB AI Symposium Frederickton, Canada (1993).

Subjects:All uncategorized technical reports
ID code:00000059
Deposited by:Staff Account on 21 October 1993



Contact site administrator at: ssg@cs.iastate.edu