# 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 deletion-closed 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 deletion-closed languages is deletion-closed.

Given a language $L$, the intersection of all deletion-closed languages containing $L$, denoted by $\operatorname{Del}(L)$, is called the deletion-closure of $L$. In other words, $\operatorname{Del}(L)$ is the smallest deletion-closed language containing $L$.

The deletion-closure 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)$.

• However, $\mathscr{F}$, the family of context-free 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 2013-03-22 18:56:23 Last modified on 2013-03-22 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 deletion-closed Synonym deletion-closure Related topic ShuffleOfLanguages Related topic InsertionOperationOnLanguages Defines deletion Defines deletion closed Defines deletion closure