insertion operation on languages


Let Σ be an alphabet, and u,v words over Σ. An insertion of u into v is a word of the form v1uv2, where v=v1v2. The concatenationMathworldPlanetmath 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 vu.

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

L1L2={uvuL1,vL2}.

So uv={u}{v}.

A language L is said to be insertion closed if LLL. Clearly Σ* is insertion closed, and arbitrary intersectionMathworldPlanetmath 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 conceptMathworldPlanetmath 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

v1u1vkukvk+1

where u=u1uk and v=v1vk+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=aba, v=bab, and w=bababa. Then

  • w is an insertion of u into v, as well as an insertion of v into u, for w=vuλ=λvu.

  • w is also a 2-insertion of u into v:

    • the decompositions u=(ab)(a) and v=(b)(ab)λ

    • or the decompositions u=λu and v=λvλ

    produce (b)(ab)(ab)(a)λ=λλvuλ=w.

  • Finally, w is also a 2-insertion of v into u, as the decompositions u=λuλ and v=vλ produce λvuλλ=w.

  • uv={ababab,babaab,baabab,bababa}.

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,

u[k]v(u[k+1]v)(v[k+1]u).

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 uL1 and vL2.

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).
Title insertion operation on languages
Canonical name InsertionOperationOnLanguages
Date of creation 2013-03-22 18:56:53
Last modified on 2013-03-22 18:56:53
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 6
Author CWoo (3771)
Entry type Definition
Classification msc 68Q70
Classification msc 68Q45
Synonym insertion-closed
Synonym insertion-closure
Related topic DeletionOperationOnLanguages
Related topic ShuffleOfLanguages
Defines insertion
Defines insertion closed
Defines insertion closure
Defines k-insertion