Figure 12.11
Theorem 12.5
Let G = (V,T,S,P) be any 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 12.8. Then the pair (A, B) permits an MPC solution if and
only if w ∈ L(G).
Proof: The proof involves a formal inductive argument based on the outlined
reasoning. We will omit the details.
With this result, we can reduce the membership problem for recursively
enumerable languages to the modified Post correspondence problem and thereby
demonstrate the undecidability of the latter.
Theorem 12.6
The modified Post correspondence problem is undecidable.
Proof: Given any unrestricted grammar G = (V,T,S,P ) and w ∈ T + , we construct
the sets A and B as suggested above. By Theorem 12.5, the pair (A, B)has an
Theorem 12.5
Let G = (V,T,S,P) be any 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 12.8. Then the pair (A, B) permits an MPC solution if and
only if w ∈ L(G).
Proof: The proof involves a formal inductive argument based on the outlined
reasoning. We will omit the details.
With this result, we can reduce the membership problem for recursively
enumerable languages to the modified Post correspondence problem and thereby
demonstrate the undecidability of the latter.
Theorem 12.6
The modified Post correspondence problem is undecidable.
Proof: Given any unrestricted grammar G = (V,T,S,P ) and w ∈ T + , we construct
the sets A and B as suggested above. By Theorem 12.5, the pair (A, B)has an