insertion operation on languages

Let $\mathrm{\Sigma }$ be an alphabet, and $u,v$ words over $\mathrm{\Sigma }$. An insertion of $u$ into $v$ is a word of the form $v_{1}u{v}_2$, where $v=v_1{v}_2$. The concatenation of two words is just a special case of insertion. Also, if $w$ is an insertion of $u$ into $v$, then $v$ is a deletion of $u$ from $w$.

The insertion of $u$ into $v$ is the set of all insertions of $v$ into $u$, and is denoted by $v⊳u$.

The notion of insertion can be extended to languages. Let $L_1,L_2$ be two languages over $\mathrm{\Sigma }$. The insertion of $L_1$ into $L_2$, denoted by $L_1⊳L_2$, is the set of all insertions of words in $L_1$ into words in $L_2$. In other words,

$$L_1⊳L_2=\bigcup \{u⊳v\mid u\in L_1,v\in L_2\}.$$

So $u⊳v=\{u\}⊳\{v\}$.

A language $L$ is said to be insertion closed if $L⊳L\subseteq L$. Clearly ${\mathrm{\Sigma }}^{*}$ is insertion closed, and arbitrary intersection of insertion closed languages is insertion closed. Given a language $L$, the insertion closure of $L$, denoted by $\mathrm{Ins}(L)$, is the smallest insertion closed language containing $L$. It is clear that $\mathrm{Ins}(L)$ exists and is unique.

More to come…

The concept of insertion can be generalized. Instead of the insertion of $u$ into $v$ taking place in one location in $v$, the insertion can take place in several locations, provided that $u$ must also be broken up into pieces so that each individual piece goes into each inserting location. More precisely, given a positive integer $k$, a $k$-insertion of $u$ into $v$ is a word of the form

$$v_1{u}_1\mathrm{\cdots }{v}_k{u}_k{v}_{k+1}$$

where $u=u_1\mathrm{\cdots }{u}_k$ and $v=v_1\mathrm{\cdots }{v}_{k+1}$. So an insertion is just a $1$-insertion. The $k$-insertion of $u$ into $v$ is the set of all $k$-insertions of $u$ into $v$, and is denoted by $u{⊳}^{[k]}v$. Clearly ${⊳}^{[1]}=⊳$.

Example. Let $\mathrm{\Sigma }=\{a,b\}$, and $u=aba$, $v=bab$, and $w=bababa$. Then

• $w$ is an insertion of $u$ into $v$, as well as an insertion of $v$ into $u$, for $w=vu\lambda =\lambda vu$.

• $w$ is also a $2$-insertion of $u$ into $v$:

  • the decompositions $u=(ab)(a)$ and $v=(b)(ab)\lambda$

  • or the decompositions $u=\lambda u$ and $v=\lambda v\lambda$

  produce $(b)(ab)(ab)(a)\lambda =\lambda \lambda vu\lambda =w$.

• Finally, $w$ is also a $2$-insertion of $v$ into $u$, as the decompositions $u=\lambda u\lambda$ and $v=v\lambda$ produce $\lambda vu\lambda \lambda =w$.

• $u⊳v=\{ababab,babaab,baabab,bababa\}$.

From this example, we observe that a $k$-insertion is a $(k+1)$-insertion, and every $k$-insertion of $u$ into $v$ is a $(k+1)$-insertion of $v$ into $u$. As a result,

$$u{⊳}^{[k]}v\subseteq (u{⊳}^{[k+1]}v)\cap (v{⊳}^{[k+1]}u).$$

As before, given languages $L_1$ and $L_2$, the $k$-insertion of $L_1$ into $L_2$, denoted by $L_1{⊳}^{[k]}{L}_2$, is the union of all $u{⊳}^{[k]}v$, where $u\in L_1$ and $v\in L_2$.

Remark. Some closure properties regarding insertions: let $ℛ$ be the family of regular languages, and $ℱ$ the family of context-free languages. Then $ℛ$ is closed under ${⊳}^{[k]}$, for each positive integer $k$. $ℱ$ is closed ${⊳}^{[k]}$ only when $k=1$. If $L_1\in ℛ$ and $L_2\in ℱ$, then $L_1{⊳}^{[k]}{L}_2$ and $L_2{⊳}^{[k]}{L}_1$ are both in $ℱ$. The proofs of these closure properties can be found in the reference.