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