Fuzzy Approach to Erroneous Inputs in Context-Free Language Recognition

摘要

In this paper, we introduce a generalization of fuzzy context-free grammars, theso-called fuzzy context-free K-grammars, to model the situation of making a finite choice out of an infinity of possible grammatical errors during each context-free derivation step. Our first result characterizes the generating capacity of these fuzzy context-free K-grammars. As consequences, we obtain: (1) bounds on modeling grammatical errors within the framework of fuzzy context-free grammars, and (2) the fact that the family of languages generated by fuzzy context-free K-grammars shares closure properties very similar to those of the family of ordinary context-free languages. The second part of the paper is devoted to a few algorithms to recognize fuzzy context-free languages: viz. a variant of a functional version of Cocke-Younger-Kasami's algorithm and some recursive descent algorithms.