insertion operation on languages
Let be an alphabet, and words over . An insertion of into is a word of the form , where . The concatenation of two words is just a special case of insertion. Also, if is an insertion of into , then is a deletion of from .
The insertion of into is the set of all insertions of into , and is denoted by .
The notion of insertion can be extended to languages. Let be two languages over . The insertion of into , denoted by , is the set of all insertions of words in into words in . In other words,
So .
A language is said to be insertion closed if . Clearly is insertion closed, and arbitrary intersection of insertion closed languages is insertion closed. Given a language , the insertion closure of , denoted by , is the smallest insertion closed language containing . It is clear that exists and is unique.
More to come…
The concept of insertion can be generalized. Instead of the insertion of into taking place in one location in , the insertion can take place in several locations, provided that must also be broken up into pieces so that each individual piece goes into each inserting location. More precisely, given a positive integer , a -insertion of into is a word of the form
where and . So an insertion is just a -insertion. The -insertion of into is the set of all -insertions of into , and is denoted by . Clearly .
Example. Let , and , , and . Then
- •
is an insertion of into , as well as an insertion of into , for .
- •
is also a -insertion of into :
- –
the decompositions and
- –
or the decompositions and
produce .
- –
- •
Finally, is also a -insertion of into , as the decompositions and produce .
- •
.
From this example, we observe that a -insertion is a -insertion, and every -insertion of into is a -insertion of into . As a result,
As before, given languages and , the -insertion of into , denoted by , is the union of all , where and .
Remark. Some closure properties regarding insertions: let be the family of regular languages, and the family of context-free languages. Then is closed under , for each positive integer . is closed only when . If and , then and 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).