Learning Languages Generated by Elementary Formal Systems and Its Application to SH Languages

Abstract

The Elementary Formal Systems ( EFSs , for short) are originally introduced by Smullyan to develop his recursion theory. In a word, EFSs are a kind of logic programs which use strings instead of terms in first order logic, and they are shown to be natural devices to define languages. In defining languages of EFSs, many studies assume that substitutions are nonerasing. A substitution or a nonerasing substitution is defined as a homomorphism from nonempty strings to nonempty strings that maps each constant symbol to itself, although an erasing substitution allows mapping of variables to the empty string. In this paper, we investigate the learnability of language classes generated by simple formal systems ( SFSs , for short) as well as regular formal systems ( RFSs , for short). We show that the learnability of some classes of their languages varies according to whether or not erasing substitutions are allowed. Then we present a subclass of RFSs such that the corresponding class of languages is inferable in the limit from positive examples, even when erasing substitutions are allowed. We also apply the obtained result to the learning problem of languages generated by simple H systems. The simple H systems ( SH systems , for short) are introduced by Mateescu et al. by modeling the recombinant behavior of DNA sequences. We show that an SH system can be naturally converted into an RFS whose language coincides with the language generated by the original SH system. By using this conversion, we show that the class of languages generated by a certain subclass of SH systems is inferable in the limit from positive examples.