|
Let $\Sigma$ be an alphabet and $u,v$ be words over $\Sigma$ . A deletion of $v$ from $u$ is a word of the form $u_1u_2$ , where $u=u_1vu_2$ . If $w$ is a deletion of $v$ from $u$ , then $u$ is an insertion of $v$ into $w$ .
The deletion of $v$ from $u$ is the set of all deletions of $v$ from $u$ , and is denoted by $u \longrightarrow v$ .
For example, if $u=(ab)^6$ and $v=aba$ , then $$u\longrightarrow v = \lbrace (ba)^4b, ab(ba)^3b, (ab)^2(ba)^2b, (ab)^3bab, (ab)^4 b\rbrace.$$
More generally, given two languages $L_1,L_2$ over $\Sigma$ , the deletion of $L_2$ from $L_1$ is the set $$L_1 \longrightarrow L_2: = \bigcup \lbrace u\longrightarrow v\mid u \in L_1, v\in L_2 \rbrace.$$
For example, if $L_1=\lbrace (ab)^n \mid n \ge 0\rbrace$ and $L_2 = \lbrace a^n b^n \mid n \ge 0\rbrace$ , then $L_1 \longrightarrow L_2 = L_1$ , and $L_2 \longrightarrow L_1 = L_2$ . If $L_3 = \lbrace a^n \mid n\ge 0\rbrace$ , then $L_2 \longrightarrow L_3 = a^m b^n \mid n\ge m \ge 0 \rbrace$ , and $L_3 \longrightarrow L_2 = L_3$ .
A language $L$ is said to be deletion-closed if $L \longrightarrow L \subseteq L$ . $L_1,L_2$ , and $L_3$ from above are all deletion closed, as well as the most obvious example: $\Sigma^*$ . $L_2\longrightarrow L_3$ is not deletion closed, for $a^3b^4 \longrightarrow ab^3 = \lbrace a^2b \rbrace \nsubseteq L_2\longrightarrow L_3$ .
It is easy to see that arbitrary intersections of deletion-closed languages is deletion-closed.
Given a language $L$ , the intersection of all deletion-closed languages containing $L$ , denoted by $\operatorname{Del}(L)$ , is called the deletion-closure of $L$ . In other words, $\operatorname{Del}(L)$ is the smallest deletion-closed language containing $L$ .
The deletion-closure of a language $L$ can be constructed from $L$ , as follows: \begin{eqnarray*} L_0 &:=& L \\ L_{n+1} &:=& L_n \longrightarrow (L_n \cup \lbrace \lambda \rbrace) \\ L' &:=& \bigcup_{i=0}^{\infty} L_i \end{eqnarray*}Then $\operatorname{Del}(L) = L'$ .
For example, if $L=\lbrace a^p \mid p \mbox{ is a prime number }\rbrace$ , then $\operatorname{Del}(L)=\lbrace a^n \mid n\ge 0 \rbrace$ , and if $L=\lbrace a^m b^n \mid m\ge n\ge 0\rbrace$ , then $\operatorname{Del}(L)=\lbrace a^m b^n \mid m,n\ge 0 \rbrace$ .
Remarks.
- 1
- M. Ito, Algebraic Theory of Automata and Languages, World Scientific, Singapore (2004).
|
