Based on the ideas suggested in [5], the following model for learning from a variant of correction queries to an oracle is proposed: being asked a membership query, the oracle, in the case of negative answer, returns also a correction - a positive datum (that has not been seen in the learning process yet) with the smallest edit distance from the queried string. Polynomial-time algorithms for learning a class of regular expressions from one such query and membership queries and learning pattern languages from queries of this type are proposed and discussed.
展开▼
