Affiliations: Institute of Mathematics of the Romanian Academy, PO Box 1 - 764, 70700 Bucureşti, Romania. e-mail: gpaun@imar.ro | Institute of Mathematics, Warsaw University of Technology, Pl. Politechniki 1, 00-650 Warsaw, Poland. e-mail: polk@mimuw.edu.pl | Institute of Mathematics, Warsaw University, Banacha 2, 02-097 Warsaw, Poland. e-mail: skowron@mimuw.edu.pl
Note: [] Work supported by the Academy of Finland, Project 11281, and the Polish Committee for Scientific Research, KBN, Grant 8T11C01011
Note: [] Work supported by the Polish Committee for Scientific Research, KBN, Grant 8T11C01011
Note: [] Work supported by the Polish Committee for Scientific Research, KBN, Grant 8T11C01011
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.
