# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### Appearance Checking: An Additional Feature
Furthermore, the first rule of any matrix of \(\mathit{MID}_{\xi}^{\prime}\) does not involve any nonterminals in \(V^{\prime}\setminus V\). Consider a sentential form \(w_{1}(i,j)w_{2}\) with \(w_{1},w_{2}\in V^{*}\). It can be shown that all the sentential forms of \(\mathit{MID}_{\xi}^{\prime}\) are either of this form or of the form \(w\in V^{*}\). The basic idea is that the nonterminal \((i,j)\) serves as an indicator where the matrix is to be applied next. For instance, the occurrence of \((i,j)\) in \(w_{1}(i,j)w_{2}\) signifies that the next rule to be applied is either \((r_{j},(\lambda,(i,j)\to(i,j+1),\lambda))\) if the length of the matrix of \(\mathit{MID}_{\xi}\) labelled by \(i\) is greater than \(j\) or \((r_{j},(\lambda,(i,j)\to(i^{\prime},1),\lambda))\) / \((r_{j},(\lambda,(i,j),\lambda)_{\text{del}})\), otherwise. We note that, in every derivation of \(\mathit{MID}_{\xi}^{\prime}\), a matrix of the form \((r_{j},(\lambda,(i,j),\lambda)_{\text{del}})\) is applied at most once. Furthermore, we remark that, if a sentential form \(w\in V^{*}\) occurs during a derivation of \(\mathit{MID}_{\xi}^{\prime}\), then the derivation cannot proceed as the second rule of any matrix cannot be applied. We now prove the correctness of the construction, i.e., \(L(\mathit{MID}_{\xi})=L(\mathit{MID}_{\xi}^{\prime})\), by showing both inclusion directions separately. '\(\supseteq\)': Consider the following derivation \(w_{1}(i,j)w_{2}\Longrightarrow_{[r,(\lambda,(i,j)\to(i^{\prime},j),\lambda)]}w _{1}^{\prime}(i^{\prime},j^{\prime})w_{2}^{\prime}\), where \(r\) is some insertion, deletion, or substitution rule and \(w_{1},w_{2}\in V^{*}\). because \(r\) does not involve any nonterminals in \(V^{\prime}\setminus V\), clearly \(w_{1}w_{2}\Longrightarrow_{r}w_{1}^{\prime}w_{2}^{\prime}\) holds. We now extend this result. Consider a matrix \(m=[r_{1},\ldots,r_{n}]\) labelled by \(i\): Subsequently, clearly  
\[w_{1}(i,1)w_{2}\Longrightarrow_{[r_{1},(\lambda,(i,1)\to(i,2),\lambda)]}\cdots \underbrace{\Longrightarrow}_{[r_{n-1},(\lambda,(i,n-1)\to(i,n),\lambda)]}w_{1} ^{\prime}(i,n)w_{2}^{\prime}\Longrightarrow_{[r_{n},(\lambda,(i,n)\to(i^{ \prime},1),\lambda)]}w_{1}^{\prime\prime}(i^{\prime},1)w_{2}^{\prime\prime}\]  
or  
\[w_{1}(i,1)w_{2}\Longrightarrow_{[r_{1},(\lambda,(i,1)\to(i,2),\lambda)]}\cdots \underbrace{\Longrightarrow}_{[r_{n-1},(\lambda,(i,n-1)\to(i,n),\lambda)]}w_{1} ^{\prime}(i,n)w_{2}^{\prime}\Longrightarrow_{[r_{n},(\lambda,(i,n),\lambda)_{ \text{del}}]}w_{1}^{\prime\prime}w_{2}^{\prime\prime}\]  
implies \(w_{1}w_{2}\Longrightarrow_{[r_{1},\ldots,r_{n}]}w_{1}^{\prime\prime}w_{2}^{ \prime\prime}\). '\(\subseteq\)': Conversely, it can be shown that \(w\Longrightarrow_{[r_{1},\ldots,r_{n}]}w^{\prime\prime}\) implies  
\[w(i,1)\Longrightarrow_{[r_{1},(\lambda,(i,1)\to(i2),\lambda)]}\cdots \underbrace{\Longrightarrow}_{[r_{n-1},(\lambda,(i,\mu-1)\to(i,\mu),\lambda)]}w ^{\prime}(i,n)\qquad\qquad\stackrel{{\longrightarrow}}{{ [r_{n},(\lambda,(i,\mu)\to(i^{\prime},1),\lambda)]}}w^{\prime\prime}(i^{ \prime},1)\]and  
\[w(i,1)_{[r_{1},(\lambda,(i,1)\to(i,2),\lambda)]}\cdots[r_{n-1},(\lambda,(i,n-1) \to(i,n),\lambda)]}w^{\prime}(i,n)\underset{[r_{n},(\lambda,(i,n),\lambda)_{ \text{del}}]}{\Longrightarrow}w^{\prime\prime}\]  
We remark that, in the simulation of the application a matrix of \(MID_{\zeta}\), we can assume that the leftmost symbol of any sentential form of a derivation of \(MID_{\zeta}^{\prime}\) is of a nonterminal \((i,j)\in V^{\prime}\setminus V\) (unless a matrix of the form \([r_{n},(\lambda,(i,n),\lambda)_{\text{del}}]\) is applied). \(\square\)  
Similarly, for every matrix ins-del-sub system \(MID_{\zeta}\in\text{MAT}_{k}\text{INS}_{n}^{m,m^{\prime}}\text{DEL}_{0}^{0,0}\)\(\text{SUB}^{r,r^{\prime}}\), one can construct \(MID_{\zeta}^{\prime}\in\text{MAT}_{2}\text{INS}_{n}^{m,m^{\prime}}\text{DEL}_{0}^{0,0} \text{SUB}^{r,r^{\prime}}\) in normal form, such that \(L(MID_{\zeta}^{\prime})=L(MID_{\zeta})\).