Recognition and learning of a class of context-sensitive languages described by augmented regular expressions

摘要

In this paper, a new formalism that permits to represent a non-trivial class of context-sensitive languages, the Augmented Regular Expressions (AREs), is introduced. AREs augment the expressive power of Regular Expressions (REs) by including a set of constraints that involve the number of instances in a string of the operands of the star operations of an RE. An efficient algorithm is given to recognize language strings by AREs. Also a general learning method to infer AREs from examples is presented, that consists of a regular grammatical inference step, a DFA to RE transformation, an RE parsing of the examples, and a constraint induction process.