$\text{Theorem}:$ Let $G = (V, T, S, P )$ be an unrestricted grammar, with w any string in $T^+$. Let $(A, B)$ be the correspondence pair constructed from $G$ and $w$ be the process exhibited in Figure. Then the pair $(A, B)$ permits an $\text{MPC}$ solution if and only if $w \in L(G)$.
| $A$ |
$B$ |
|
| $FS\Rightarrow$ |
$F$ |
$F$ is a symbol in $V\cup T$ |
| $a$ |
$a$ |
for every $a \in T$ |
| $V_i$ |
$V_i$ |
for every $V_i \in V$ |
| $E$ |
$\Rightarrow wE$ |
$E$ is a symbol not in $V\cup T$ |
| $y_i$ |
$x_i$ |
for every $x_i\rightarrow y_i$ in $P$ |
| $\Rightarrow$ |
$\Rightarrow$ |
|
$FS\Rightarrow$ is to be taken as $w_1$ and the string $F$ as $v_1$. The order of the rest of the strings is immaterial.
Provide the details of the proof of the Theorem.
