Let $\Sigma$ be an alphabet, and $u,v$ words over $\Sigma$. An insertion of $u$ into $v$ is a word of the form $v_{1}uv_{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\rhd u$.

The notion of insertion can be extended to languages. Let $L_{1},L_{2}$ be two languages over $\Sigma$. The insertion of $L_{1}$ into $L_{2}$, denoted by $L_{1}\rhd L_{2}$, is the set of all insertions of words in $L_{1}$ into words in $L_{2}$. In other words,

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

A language $L$ is said to be insertion closed if $L\rhd L\subseteq L$. Clearly $\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 $\operatorname{Ins}(L)$, is the smallest insertion closed language containing $L$. It is clear that $\operatorname{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

where $u=u_{1}\cdots u_{k}$ and $v=v_{1}\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\rhd^{{[k]}}v$. Clearly $\rhd^{{[1]}}=\rhd$.

Example. Let $\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\rhd 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,

As before, given languages $L_{1}$ and $L_{2}$, the $k$-insertion of $L_{1}$ into $L_{2}$, denoted by $L_{1}\rhd^{{[k]}}L_{2}$, is the union of all $u\rhd^{{[k]}}v$, where $u\in L_{1}$ and $v\in L_{2}$.

Remark. Some closure properties regarding insertions: let $\mathscr{R}$ be the family of regular languages, and $\mathscr{F}$ the family of context-free languages. Then $\mathscr{R}$ is closed under $\rhd^{{[k]}}$, for each positive integer $k$. $\mathscr{F}$ is closed $\rhd^{{[k]}}$ only when $k=1$. If $L_{1}\in\mathscr{R}$ and $L_{2}\in\mathscr{F}$, then $L_{1}\rhd^{{[k]}}L_{2}$ and $L_{2}\rhd^{{[k]}}L_{1}$ are both in $\mathscr{F}$. The proofs of these closure properties can be found in the reference.