INSERTION AND ITERATED INSERTION AS OPERATIONS ON FORMAL LANGUAGES.

摘要

The operations of insertion ((<---)) and iterated insertion ((<---)*) are simple variants of Kleene's operations (.) and (,*) ({Kle 56}) in a manner similar to the operations shuffle and iterated shuffle (see e.g. {Jan 81}). Using the operation of iterated insertion, we can generate both the semi-Dyck and the two-sided Dyck languages (see e.g. {Har 78}) from certain finite subsets of these languages. Thus the class of languages of the form S('(<---)*) for finite S forms a natural class of generalized Dyck languages. We present several combinatorial results that demonstrate that the problems of equivalence, of ambiguous representation, of confluence (see {Bk 82}) and of regularity are decidable for this class of languages. In obtaining the latter result, we give two important general results involving the application of the theory of well quasi orders (see e.g. {Kru 72}) to the study of regular languages. On the other hand, we show that the problem "S('(<---)*) (INTERSECT) T('(<---)*) = {(lamda)}?" is undecidable for finite, unambiguous S and T. Furthermore, by extending the regular expressions to include the operations (<---) and (<---)(,*) we obtain the class of insertion languages which generalizes both the regular languages and the Dyck languages, but is properly contained within the class of context-free languages. Our main result here is that the problem "L = (SIGMA)('*)?" is undecidable for the class of insertion languages. From this result, it follows that the equivalence problem and the problem "Is L regular?" are also undecidable for this class.