You are here
Homeinsertion operation on languages
Primary tabs
insertion operation on languages
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,
$L_{1}\rhd L_{2}=\bigcup\{u\rhd v\mid u\in L_{1},v\in L_{2}\}.$ 
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
$v_{1}u_{1}\cdots v_{k}u_{k}v_{{k+1}}$ 
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,
$u\rhd^{{[k]}}v\subseteq(u\rhd^{{[k+1]}}v)\cap(v\rhd^{{[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}\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 contextfree 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.
References
 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Mathematics Subject Classification
68Q70 no label found68Q45 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections