Insertion languages (Q796994)

The operations of insertion (\(\leftarrow)\) and iterated insertion (\(\leftarrow *)\) are variants of Kleene's operations \(\cdot\) and *. For languages S and T, \(S\leftarrow T=\{xzy:xy\in S\quad and\quad z\in T\}\) and \(S\leftarrow *=\{\lambda \}\cup S\cup S\leftarrow S\cup...\) (where \(\lambda\) is the empty word). The class of languages of the form \(S\leftarrow *\) for finite S forms a class of generalized Dyck languages. The problems of equivalence, ambiguity and determinism are investigated for this class and all are shown to be decidable. On the other hand, it is shown that the problem \(''S\leftarrow *T\leftarrow *=\{\lambda \}?''\) is undecidable for finite unambiguous S and T. By extending the regular expressions to include the operations \(\leftarrow\) and \(\leftarrow *\), the class of insertion languages is obtained, which includes both the regular languages and the Dyck languages, but is properly contained in the class of context-free languages. It is shown that the problem \(''L=\Sigma *?''\) is undecidable for the class of insertion languages. From this it follows that the equivalence problem and the problem ''Is L regular?'' are also undecidable for this class.