deletion operation on languages
The deletion of from is the set of all deletions of from , and is denoted by .
For example, if and , then
More generally, given two languages over , the deletion of from is the set
For example, if and , then , and . If , then , and .
A language is said to be deletion-closed if . , and from above are all deletion closed, as well as the most obvious example: . is not deletion closed, for .
It is easy to see that arbitrary intersections of deletion-closed languages is deletion-closed.
Given a language , the intersection of all deletion-closed languages containing , denoted by , is called the deletion-closure of . In other words, is the smallest deletion-closed language containing .
The deletion-closure of a language can be constructed from , as follows:
For example, if , then , and if , then .
However, , the family of context-free languages, is neither closed under deletion, nor under deletion closure.
- 1 M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
|Title||deletion operation on languages|
|Date of creation||2013-03-22 18:56:23|
|Last modified on||2013-03-22 18:56:23|
|Last modified by||CWoo (3771)|