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).
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 | -insertion |