insertion operation on languages (original) (raw)

Let Σ be an alphabet, and u,v words over Σ. An insertion of u into v is a word of the form v1⁢u⁢v2, where v=v1⁢v2. The concatenation of two words is just a special case of insertion. Also, if w is an insertion of u into v, then v is a deletion of u from w.

The insertion of u into v is the set of all insertions of v into u, and is denoted by v⊳u.

The notion of insertion can be extended to languages. Let L1,L2 be two languages over Σ. The insertion of L1 into L2, denoted by L1⊳L2, is the set of all insertions of words in L1 into words in L2. In other words,

So u⊳v={u}⊳{v}.

A language L is said to be insertion closed if L⊳L⊆L. Clearly Σ* is insertion closed, and arbitrary intersection of insertion closed languages is insertion closed. Given a language L, the insertion closure of L, denoted by Ins⁡(L), is the smallest insertion closed language containing L. It is clear that Ins⁡(L) exists and is unique.

More to come…

The concept of insertion can be generalized. Instead of the insertion of u into v taking place in one location in v, the insertion can take place in several locations, provided that u must also be broken up into pieces so that each individual piece goes into each inserting location. More precisely, given a positive integer k, a k-insertion of u into v is a word of the form

where u=u1⁢⋯⁢uk and v=v1⁢⋯⁢vk+1. So an insertion is just a 1-insertion. The k-insertion of u into v is the set of all k-insertions of u into v, and is denoted by u⊳[k]v. Clearly ⊳[1]⁣=⁣⊳.

Example. Let Σ={a,b}, and u=a⁢b⁢a, v=b⁢a⁢b, and w=b⁢a⁢b⁢a⁢b⁢a. Then

• •
  w is an insertion of u into v, as well as an insertion of v into u, for w=v⁢u⁢λ=λ⁢v⁢u.
• •
  w is also a 2-insertion of u into v:
  • –
    the decompositions u=(a⁢b)⁢(a) and v=(b)⁢(a⁢b)⁢λ
  • –
    or the decompositions u=λ⁢u and v=λ⁢v⁢λ
    produce (b)⁢(a⁢b)⁢(a⁢b)⁢(a)⁢λ=λ⁢λ⁢v⁢u⁢λ=w.
• •
  Finally, w is also a 2-insertion of v into u, as the decompositions u=λ⁢u⁢λ and v=v⁢λ produce λ⁢v⁢u⁢λ⁢λ=w.
• •
  u⊳v={a⁢b⁢a⁢b⁢a⁢b,b⁢a⁢b⁢a⁢a⁢b,b⁢a⁢a⁢b⁢a⁢b,b⁢a⁢b⁢a⁢b⁢a}.

From this example, we observe that a k-insertion is a (k+1)-insertion, and every k-insertion of u into v is a (k+1)-insertion of v into u. As a result,

As before, given languages L1 and L2, the k-insertion of L1 into L2, denoted by L1⊳[k]L2, is the union of all u⊳[k]v, where u∈L1 and v∈L2.

Remark. Some closure properties regarding insertions: let ℛ be the family of regular languages, and ℱ the family of context-free languages. Then ℛ is closed under ⊳[k], for each positive integer k. ℱ is closed ⊳[k] only when k=1. If L1∈ℛ and L2∈ℱ, then L1⊳[k]L2 and L2⊳[k]L1 are both in ℱ. The proofs of these closure properties can be found in the reference.

References

• 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).