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\u22b3u$.
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}\u22b3{L}_{2}$, is the set of all insertions of words in ${L}_{1}$ into words in ${L}_{2}$. In other words,
$${L}_{1}\u22b3{L}_{2}=\bigcup \{u\u22b3v\mid u\in {L}_{1},v\in {L}_{2}\}.$$ 
So $u\u22b3v=\{u\}\u22b3\{v\}$.
A language $L$ is said to be insertion closed if $L\u22b3L\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{\u22b3}^{[k]}v$. Clearly ${\u22b3}^{[1]}=\u22b3$.
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\u22b3v=\{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{\u22b3}^{[k]}v\subseteq (u{\u22b3}^{[k+1]}v)\cap (v{\u22b3}^{[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}{\u22b3}^{[k]}{L}_{2}$, is the union of all $u{\u22b3}^{[k]}v$, where $u\in {L}_{1}$ and $v\in {L}_{2}$.
Remark. Some closure properties regarding insertions: let $\mathcal{R}$ be the family of regular languages, and $\mathcal{F}$ the family of contextfree languages. Then $\mathcal{R}$ is closed under ${\u22b3}^{[k]}$, for each positive integer $k$. $\mathcal{F}$ is closed ${\u22b3}^{[k]}$ only when $k=1$. If ${L}_{1}\in \mathcal{R}$ and ${L}_{2}\in \mathcal{F}$, then ${L}_{1}{\u22b3}^{[k]}{L}_{2}$ and ${L}_{2}{\u22b3}^{[k]}{L}_{1}$ are both in $\mathcal{F}$. The proofs of these closure properties can be found in the reference.
References
 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Title  insertion operation on languages 
Canonical name  InsertionOperationOnLanguages 
Date of creation  20130322 18:56:53 
Last modified on  20130322 18:56:53 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  6 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 68Q45 
Synonym  insertionclosed 
Synonym  insertionclosure 
Related topic  DeletionOperationOnLanguages 
Related topic  ShuffleOfLanguages 
Defines  insertion 
Defines  insertion closed 
Defines  insertion closure 
Defines  $k$insertion 