Abstract
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 malting 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 tum out to be robust in some very elementary sense and they can easily be extended to corresponding parsing algorithms.- Anthology ID:
- 1995.iwpt-1.5
- Volume:
- Proceedings of the Fourth International Workshop on Parsing Technologies
- Month:
- September 20-24
- Year:
- 1995
- Address:
- Prague and Karlovy Vary, Czech Republic
- Editors:
- Eva Hajicova, Bernard Lang, Robert Berwick, Harry Bunt, Bob Carpenter, Ken Church, Aravind Joshi, Ronald Kaplan, Martin Kay, Makoto Nagao, Anton Nijholt, Mark Steedman, Henry Thompson, Masaru Tomita, K. Vijay-Shanker, Yorick Wilks, Kent Wittenburg
- Venues:
- IWPT | WS
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 14–25
- Language:
- URL:
- https://aclanthology.org/1995.iwpt-1.5
- DOI:
- Cite (ACL):
- Peter R.J. Asveld. 1995. A Fuzzy Approach to Erroneous Inputs in Context-Free Language Recognition. In Proceedings of the Fourth International Workshop on Parsing Technologies, pages 14–25, Prague and Karlovy Vary, Czech Republic. Association for Computational Linguistics.
- Cite (Informal):
- A Fuzzy Approach to Erroneous Inputs in Context-Free Language Recognition (Asveld, IWPT-WS 1995)
- PDF:
- https://preview.aclanthology.org/nschneid-patch-4/1995.iwpt-1.5.pdf