Abstract
We investigate here the possibility of approximating a language starting from a partial knowledge of its strings. This is understood as the possibility to read only a bounded part of a string: a prefix or a subword. In this way, indiscernibility relations among strings (they are equivalence or tolerance relations) are introduced, which lead to lower and upper approximations of languages. By varying the length of the perceived substring, we get sequences of approximations converging to the language. In many cases, the approximations of context-free languages are proved to be regular languages.
Get full access to this article
View all access options for this article.