You are here
Homedeletion operation on languages
Primary tabs
deletion operation on languages
Let $\Sigma$ be an alphabet and $u,v$ be words over $\Sigma$. A deletion of $v$ from $u$ is a word of the form $u_{1}u_{2}$, where $u=u_{1}vu_{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\longrightarrow v$.
For example, if $u=(ab)^{6}$ and $v=aba$, then
$u\longrightarrow v=\{(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 $\Sigma$, the deletion of $L_{2}$ from $L_{1}$ is the set
$L_{1}\longrightarrow L_{2}:=\bigcup\{u\longrightarrow v\mid u\in L_{1},v\in L_% {2}\}.$ 
For example, if $L_{1}=\{(ab)^{n}\mid n\geq 0\}$ and $L_{2}=\{a^{n}b^{n}\mid n\geq 0\}$, then $L_{1}\longrightarrow L_{2}=L_{1}$, and $L_{2}\longrightarrow L_{1}=L_{2}$. If $L_{3}=\{a^{n}\mid n\geq 0\}$, then $L_{2}\longrightarrow L_{3}=a^{m}b^{n}\mid n\geq m\geq 0\}$, and $L_{3}\longrightarrow L_{2}=L_{3}$.
A language $L$ is said to be deletionclosed if $L\longrightarrow L\subseteq L$. $L_{1},L_{2}$, and $L_{3}$ from above are all deletion closed, as well as the most obvious example: $\Sigma^{*}$. $L_{2}\longrightarrow L_{3}$ is not deletion closed, for $a^{3}b^{4}\longrightarrow ab^{3}=\{a^{2}b\}\nsubseteq L_{2}\longrightarrow 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 $\operatorname{Del}(L)$, is called the deletionclosure of $L$. In other words, $\operatorname{Del}(L)$ is the smallest deletionclosed language containing $L$.
The deletionclosure of a language $L$ can be constructed from $L$, as follows:
$\displaystyle L_{0}$  $\displaystyle:=$  $\displaystyle L$  
$\displaystyle L_{{n+1}}$  $\displaystyle:=$  $\displaystyle L_{n}\longrightarrow(L_{n}\cup\{\lambda\})$  
$\displaystyle L^{{\prime}}$  $\displaystyle:=$  $\displaystyle\bigcup_{{i=0}}^{{\infty}}L_{i}$ 
Then $\operatorname{Del}(L)=L^{{\prime}}$.
For example, if $L=\{a^{p}\mid p\mbox{ is a prime number }\}$, then $\operatorname{Del}(L)=\{a^{n}\mid n\geq 0\}$, and if $L=\{a^{m}b^{n}\mid m\geq n\geq 0\}$, then $\operatorname{Del}(L)=\{a^{m}b^{n}\mid m,n\geq 0\}$.
Remarks.

If $L_{1},L_{2}$ are regular languages, so is $L_{1}\longrightarrow L_{2}$. In other words, the family $\mathscr{R}$ of regular languages is closed under the deletion binary operation.

In addition, $\mathscr{R}$ is closed under deletion closure: if $L$ is regular, so is $\operatorname{Del}(L)$.
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