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

PATTERN RECOGNITION

卷:30

Article

Alquezar, R ; Sanfeliu, A

关键词: context-sensitive languages;    finite automata;    formal languages;    grammatical inference;    learning;    parsing;    regular expressions;    syntactic pattern recognition;   

DOI  :  10.1016/S0031-3203(96)00056-8

来源: Elsevier

【 摘 要 】

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. Copyright (C) 1996 Pattern Recognition Society.

【 授权许可】

Free