# Adding Matrix Control: Insertion-Deletion Systems with Substitutions III
## 2 Definitions
### One-Sided Context Dependence
#### 3.2.2 Computational Incompleteness  
Though ins-del systems with matrix control and substitution rules are powerful devices, they are not always sufficient for achieving computational completeness. **Lemma 3**. : _Let \(\mathit{MID}_{\xi}\) be a a matrix ins-del-sub systems of size \((*;1,1,0;1,0,0;0,0)\). Subsequently, \(L(\mathit{MID}_{\xi})\in\mathcal{L}(M,\mathit{CF})\)._  
Proof. : Let \(\mathit{MID}_{\xi}=(V,T,A,M_{\xi})\) be in normal form and constructed according to the construction in Theorem 2. Subsequently, we construct the following matrix grammar \(G=(N,T,M_{G},S)\) with \(N=\{N_{a}\mid a\in V\}\). For every \(\alpha_{1}\ldots\alpha_{n}\in A\), we add a matrix \([S\to N_{a_{1}}\ldots N_{a_{n}}]\) to \(M_{G}\). For every matrix of the form \(X\) of \(\mathit{MID}_{\xi}\), we add a matrix of the form \(Y\) to \(M_{G}\). \[ \begin{array}{ll}\text{form }X&\text{form }Y\\ \hline[(\lambda,b,\lambda)_{\text{del}},(\lambda,c\to d,\lambda)]&[N_{b}\to \lambda,N_{c}\to N_{d}]\\ [(\lambda,b,\lambda)_{\text{del}},(\lambda,c,\lambda)_{\text{del}}]&[N_{b}\to \lambda,N_{c}\to\lambda]\\ [(\lambda,b\to b^{\prime},\lambda),(\lambda,c\to d,\lambda)]&[N_{b}\to N_{b^{ \prime}},N_{c}\to N_{d}]\\ [(\lambda,b\to b^{\prime},\lambda),(\lambda,c,\lambda)_{\text{del}}]&[N_{b}\to N _{b^{\prime}},N_{c}\to\lambda]\\ [(a,b,\lambda)_{\text{ins}},(\lambda,c\to d,\lambda)]&[N_{a}\to N_{a}N_{b},N_{c }\to N_{d}]\\ [(a,b,\lambda)_{\text{ins}},(\lambda,c,\lambda)_{\text{del}}]&[N_{a}\to N_{a}N _{b},N_{c}\to\lambda]\end{array} \]  
For every matrix of the form \(X^{\prime}\) of \(\mathit{MID}_{\xi}\) and every \(N_{a}\in N\), we add matrices of the form \(Y^{\prime}\) to \(M_{G}\). \[ \begin{array}{ll}\text{form }Y^{\prime}&\\ \hline[(\lambda,b,\lambda)_{\text{ins}},(\lambda,c\to d,\lambda)]&[N_{a}\to N _{a}N_{b},N_{c}\to N_{d}],[N_{a}\to N_{b}N_{a},N_{c}\to N_{d}]\\ [(\lambda,b,\lambda)_{\text{ins}},(\lambda,c,\lambda)_{\text{del}}]&[N_{a}\to N _{a}N_{b},N_{c}\to\lambda],\,[N_{a}\to N_{b}N_{a},N_{c}\to\lambda]\end{array} \]  
Furthermore, we add matrices of the form \([N_{a}\to a]\) to \(M_{G}\) if \(a\in T\). By induction, it can be shown that \(a_{1}\ldots a_{n}\Rightarrow_{G}b_{1}\ldots b_{m}\) if and only if  
\[N_{a_{1}}\ldots N_{a_{n}}\Longrightarrow_{\mathit{MID}_{\xi}}N_{b_{1}}\ldots N _{b_{m}}.\]  
Whenever a matrix \([(\lambda,b,\lambda)_{\text{ins}},(\lambda,c\to d,\lambda)]\) is applicable to \(a_{1}\ldots a_{n}\in V^{*}\), some matrix of the form \([N_{a}\to N_{a}N_{b},N_{c}\to N_{d}]\) is applicable to \(N_{a_{1}}\ldots N_{a_{n}}\in N^{*}\) and vice versa. We remark that, if a sentential form \(\lambda\) occurs during either a derivation of \(\mathit{MID}_{\xi}\) or \(G\), the derivation cannot proceed, as no matrix is applicable any more. (see Theorem 2). Hence, the case that the axiom of a derivation of \(\mathit{MID}_{\xi}\) is \(\lambda\) is covered by an application of \(S\to\lambda\). Therefore, it is easy to see that \(L(G)=L(\mathit{MID}_{\xi})\) holds. Moreover, \(L(G)\in\mathcal{L}(\text{M},\text{CF})\). Although systems of size \((2;1,1,0;1,0,0;0,0)\) do not reach computational completeness, they do characterize matrix grammars. Lemma 4: _Let \(G\) be a matrix grammar, such that \(L(G)\in\mathcal{L}(M,\text{CF})\). Subsequently, there exists a matrix ins-del system with substitution rules \(\mathit{MID}_{\xi}\) of size \((2;1,0;1,0,0;0,0)\), such that \(L(G)=L(\mathit{MID}_{\xi})\)._  
Proof: Let \(G=(N,T,M_{G},S)\) be a matrix grammar with context-free production rules. Afterwards, we construct \(\mathit{MID}_{\xi}=(V,T,A,M_{\xi})\) as follows: We define \(V=N\cup T\cup\{X\}\) and \(A=\{S\}\). Consider a context-free production rule of the form \(A\to\lambda\). Clearly, this rule is equivalent to a deletion rule \((\lambda,A,\lambda)\). Analogously, a production rule \(A\to B\) is essentially the same as a substitution rule \((\lambda,A\to B,\lambda)\).