Reduce the non-empty intersection problem on CFGs over
{a,b} to the set of
tuples of four CFGs
G1,G2,G3,G4 such that
G1 and
G2 generate at
least one common word,
G3 and
G4 generate at least one common word, but
G1 and
G4 do not generate a common word, and
G2 and
G3 do not
generate a common word, in order to prove that such set is undecidable (not
recursive).