Obviously, if (root E) = (root E') holds in the unified f-structures of the string grammars, then the unification of the string grammar f-structures and the structure in Figure 2 yields F. Otherwise, their unification results in a structure that only properly subsumes F. This is because neither (root E E) nor (root E' E) exists in the unified f-structures of the two string grammars, and therefore their values in the structure in Figure 2 are not merged when the structures are unified.
g derives with F exactly the set of strings We now give a rigorous statement and proof of our undecidability theorem.