A Fuzzy Approach to Erroneous Inputs in ContextFree Language Recognition
Asveld, Peter R.J. (1995) A Fuzzy Approach to Erroneous Inputs in ContextFree Language Recognition. [Report]

PDF
80kB 
Abstract:  Using fuzzy contextfree grammars one can easily describe a finite number of ways to derive incorrect strings together with their degree of correctness. However, in general there is an infinite number of ways to perform a certain task wrongly. In this paper we introduce a generalization of fuzzy contextfree grammars, the socalled fuzzy contextfree grammars, to model the situation of making a finite choice out of an infinity of possible grammatical errors during each contextfree derivation step. Under minor assumptions on the parameter this model happens to be a very general framework to describe correctly as well as erroneously derived sentences by a single generating mechanism.
Our first result characterizes the generating capacity of these fuzzy contextfree grammars. As consequences we obtain: (i) bounds on modeling grammatical errors within the framework of fuzzy contextfree grammars, and (ii) the fact that the family of languages generated by fuzzy contextfree grammars shares closure properties very similar to those of the family of ordinary contextfree languages. The second part of the paper is devoted to a few algorithms to recognize fuzzy contextfree languages: viz. a variant of a functional version of CockeYounger Kasami's algorithm and some recursive descent algorithms. These algorithms turn out to be robust in some very elementary sense and they can easily be extended to corresponding parsing algorithms. 
Item Type:  Report 
Faculty:  Electrical Engineering, Mathematics and Computer Science (EEMCS) 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/64293 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page
Metis ID: 118476