deletion operation on languages

Let Σ be an alphabet and u,v be words over Σ. A deletion of v from u is a word of the form u1u2, where u=u1vu2. 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 uv.

For example, if u=(ab)6 and v=aba, then


More generally, given two languagesPlanetmathPlanetmath L1,L2 over Σ, the deletion of L2 from L1 is the set


For example, if L1={(ab)nn0} and L2={anbnn0}, then L1L2=L1, and L2L1=L2. If L3={ann0}, then L2L3=ambnnm0}, and L3L2=L3.

A language L is said to be deletion-closed if LLL. L1,L2, and L3 from above are all deletion closed, as well as the most obvious example: Σ*. L2L3 is not deletion closed, for a3b4ab3={a2b}L2L3.

It is easy to see that arbitrary intersectionsMathworldPlanetmath of deletion-closed languages is deletion-closed.

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

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

L0 := L
Ln+1 := Ln(Ln{λ})
L := i=0Li

Then Del(L)=L.

For example, if L={app is a prime number }, then Del(L)={ann0}, and if L={ambnmn0}, then Del(L)={ambnm,n0}.



  • 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