A Fuzzy Approach to Erroneous Inputs in Context-Free Language Recognition

P.R.J. Asveld

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    10 Citations (Scopus)
    12 Downloads (Pure)


    Using fuzzy context-free 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 context-free grammars, the so-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. Under minor assumptions on the parameter $K$ 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 context-free $K$-grammars. As consequences we obtain: (i) bounds on modeling grammatical errors within the framework of fuzzy context-free grammars, and (ii) 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. These algorithms turn out to be robust in some very elementary sense and they can easily be extended to corresponding parsing algorithms.
    Original languageEnglish
    Title of host publicationIWPT '95, Fourth International Workshop on Parsing technologies, Prague and Karlovy Vary (Czech Republic), September 20-24, 1995
    Subtitle of host publicationworkshop proceedings
    Place of PublicationPrague
    PublisherCharles University
    Number of pages12
    Publication statusPublished - 1995
    Event4th International Workshop on Parsing Technologies, IWPT 1995 - Prague & Karlovy Vary, Czech Republic
    Duration: 20 Sep 199524 Sep 1995
    Conference number: 4


    Workshop4th International Workshop on Parsing Technologies, IWPT 1995
    Abbreviated titleIWPT
    Country/TerritoryCzech Republic
    CityPrague & Karlovy Vary


    • HMI-SLT: Speech and Language Technology


    Dive into the research topics of 'A Fuzzy Approach to Erroneous Inputs in Context-Free Language Recognition'. Together they form a unique fingerprint.

    Cite this