deletion operation on languages
Let $\mathrm{\Sigma}$ be an alphabet and $u,v$ be words over $\mathrm{\Sigma}$. A deletion of $v$ from $u$ is a word of the form ${u}_{1}{u}_{2}$, where $u={u}_{1}v{u}_{2}$. If $w$ is a deletion of $v$ from $u$, then $u$ is an insertion of $v$ into $w$.
The deletion of $v$ from $u$ is the set of all deletions of $v$ from $u$, and is denoted by $u\u27f6v$.
For example, if $u={(ab)}^{6}$ and $v=aba$, then
$$u\u27f6v=\{{(ba)}^{4}b,ab{(ba)}^{3}b,{(ab)}^{2}{(ba)}^{2}b,{(ab)}^{3}bab,{(ab)}^{4}b\}.$$ 
More generally, given two languages^{} ${L}_{1},{L}_{2}$ over $\mathrm{\Sigma}$, the deletion of ${L}_{2}$ from ${L}_{1}$ is the set
$${L}_{1}\u27f6{L}_{2}:=\bigcup \{u\u27f6v\mid u\in {L}_{1},v\in {L}_{2}\}.$$ 
For example, if ${L}_{1}=\{{(ab)}^{n}\mid n\ge 0\}$ and ${L}_{2}=\{{a}^{n}{b}^{n}\mid n\ge 0\}$, then ${L}_{1}\u27f6{L}_{2}={L}_{1}$, and ${L}_{2}\u27f6{L}_{1}={L}_{2}$. If ${L}_{3}=\{{a}^{n}\mid n\ge 0\}$, then ${L}_{2}\u27f6{L}_{3}={a}^{m}{b}^{n}\mid n\ge m\ge 0\}$, and ${L}_{3}\u27f6{L}_{2}={L}_{3}$.
A language $L$ is said to be deletionclosed if $L\u27f6L\subseteq L$. ${L}_{1},{L}_{2}$, and ${L}_{3}$ from above are all deletion closed, as well as the most obvious example: ${\mathrm{\Sigma}}^{*}$. ${L}_{2}\u27f6{L}_{3}$ is not deletion closed, for ${a}^{3}{b}^{4}\u27f6a{b}^{3}=\{{a}^{2}b\}\u2288{L}_{2}\u27f6{L}_{3}$.
It is easy to see that arbitrary intersections^{} of deletionclosed languages is deletionclosed.
Given a language $L$, the intersection of all deletionclosed languages containing $L$, denoted by $\mathrm{Del}(L)$, is called the deletionclosure of $L$. In other words, $\mathrm{Del}(L)$ is the smallest deletionclosed language containing $L$.
The deletionclosure of a language $L$ can be constructed from $L$, as follows:
${L}_{0}$  $:=$  $L$  
${L}_{n+1}$  $:=$  ${L}_{n}\u27f6({L}_{n}\cup \{\lambda \})$  
${L}^{\prime}$  $:=$  $\bigcup _{i=0}^{\mathrm{\infty}}}{L}_{i$ 
Then $\mathrm{Del}(L)={L}^{\prime}$.
For example, if $L=\{{a}^{p}\mid p\text{is a prime number}\}$, then $\mathrm{Del}(L)=\{{a}^{n}\mid n\ge 0\}$, and if $L=\{{a}^{m}{b}^{n}\mid m\ge n\ge 0\}$, then $\mathrm{Del}(L)=\{{a}^{m}{b}^{n}\mid m,n\ge 0\}$.
Remarks.

•
If ${L}_{1},{L}_{2}$ are regular languages, so is ${L}_{1}\u27f6{L}_{2}$. In other words, the family $\mathcal{R}$ of regular languages is closed under^{} the deletion binary operation^{}.
 •

•
However, $\mathcal{F}$, the family of contextfree languages, is neither closed under deletion, nor under deletion closure.
References
 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
Title  deletion operation on languages 
Canonical name  DeletionOperationOnLanguages 
Date of creation  20130322 18:56:23 
Last modified on  20130322 18:56:23 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  8 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q70 
Classification  msc 68Q45 
Synonym  deletionclosed 
Synonym  deletionclosure 
Related topic  ShuffleOfLanguages 
Related topic  InsertionOperationOnLanguages 
Defines  deletion 
Defines  deletion closed 
Defines  deletion closure 