We want to claim eventually that w ∈ L(G) if and only if the sets A and B
constructed in this way have an MPC solution. Since this is perhaps not
immediately obvious, let us illustrate it with a simple example.
Example 12.6
Let G =({A,B,C},{a,b,c,},S,P) with productions
and take w = aaac. The sequences A and B obtained from the suggested
construction are given in Figure 12.9. The string w = aaac is in L(G) and has a
derivation
S ⇒ aABb ⇒ aAC ⇒ aaac.
How this derivation is paralleled by an MPC solution with the constructed sets