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⟶v$.

For example, if $u={(ab)}^6$ and $v=aba$, then

$$u⟶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 $\mathrm{\Sigma }$, the deletion of $L_2$ from $L_1$ is the set

$$L_1⟶L_2:=\bigcup \{u⟶v\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⟶L_2=L_1$, and $L_2⟶L_1=L_2$. If $L_3=\{a^n\mid n\ge 0\}$, then $L_2⟶L_3=a^m{b}^n\mid n\ge m\ge 0\}$, and $L_3⟶L_2=L_3$.

A language $L$ is said to be deletion-closed if $L⟶L\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⟶L_3$ is not deletion closed, for $a^3{b}^4⟶a{b}^3=\{a^{2}b\}⊈L_2⟶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 $\mathrm{Del}(L)$, is called the deletion-closure of $L$. In other words, $\mathrm{Del}(L)$ is the smallest deletion-closed language containing $L$.

The deletion-closure of a language $L$ can be constructed from $L$, as follows:

$L_0$$:=$$L$

$L_{n+1}$$:=$$L_n⟶(L_n\cup \{\lambda \})$

$L^{\prime }$$:=$${\displaystyle \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⟶L_2$. In other words, the family $ℛ$ of regular languages is closed under the deletion binary operation.

• In addition, $ℛ$ is closed under deletion closure: if $L$ is regular, so is $\mathrm{Del}(L)$.

• However, $ℱ$, the family of context-free languages, is neither closed under deletion, nor under deletion closure.