INSERTION AND DELETION CLOSURE OF LANGUAGES

To a given language L, we associate the sets ins(L) (resp. del(L)) con sisting of words with the following property: their insertion into (de letion from) any word of L yields words which also belong to L. Proper ties of these sets and of languages which are insertion (deletion) clo sed are obtained. Of special interest is the case when the language is ins-closed (del-closed) and finitely generated. Then the minimal set of generators turns out to be a maximal prefix and suffix code, which is regular if L is regular. In addition, we study the insertion-base o f a language and languages which have the property that both they and their complements are ins-closed.