deletion operation on languages (original) (raw)

Let Σ be an alphabet and u,v be words over Σ. A deletion of v from u is a word of the form u1⁢u2, where u=u1⁢v⁢u2. 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=(a⁢b)6 and v=a⁢b⁢a, then

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

For example, if L1={(a⁢b)n∣n≥0} and L2={an⁢bn∣n≥0}, then L1⟶L2=L1, and L2⟶L1=L2. If L3={an∣n≥0}, then L2⟶L3=ambn∣n≥m≥0}, and L3⟶L2=L3.

A language L is said to be deletion-closed if L⟶L⊆L. L1,L2, and L3 from above are all deletion closed, as well as the most obvious example: Σ*. L2⟶L3 is not deletion closed, for a3⁢b4⟶a⁢b3={a2⁢b}⊈L2⟶L3.

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 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:

Then Del⁡(L)=L′.

For example, if L={ap∣p⁢ is a prime number }, then Del⁡(L)={an∣n≥0}, and if L={am⁢bn∣m≥n≥0}, then Del⁡(L)={am⁢bn∣m,n≥0}.

Remarks.

• •
• •
  In addition, ℛ is closed under deletion closure: if L is regular, so is Del⁡(L).
• •
  However, ℱ, 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).