|
28th Annual Conference on Current
Trends in
Theory and Practice of Informatics
|
|
November 24 - December 1, 2001
|
|
Approximative Learning of Regular Languages
by Henning Fernau
Abstract:
We show how appropriately chosen functions $f$
which we call distinguishing
can be used to make deterministic finite
automata backward deterministic. These ideas have been exploited
to design regular language classes called
$f$-distinguishable which are identifiable
in the limit from positive samples.
Special cases of this approach are the
k-reversible and terminal dis\-tin\-guish\-able languages as discussed
in several papers by Angluin, Fernau, Radhakrishnan and Nagaraja.
Here, we give new characterizations of these language classes.
Moreover, we show that all regular languages
can be approximated in the setting introduced by
Kobayashi and Yokomori in 1987.
Finally, we prove that the class of all function-distinguishable
languages is equal to the class of regular languages.