(0,1)-TOTALITY IS UNDECIDABLE FOR ARBITRARY CONTEXT-FREE GRAMMARS

This note shows that it is undecidable whether or not an arbitrary context-free grammar is (0,l)-total, i.e., whether or not {0, 1}⁺ ⊆ g(Szl(G)) holds for an arbitrary context-free grammar G, the left Szilard language Szl(G) of G, and a homomorphism g mapping the labels of G's productions into {0, 1} ∪ {λ}. These considerations are motivated by cryptosystems recently proposed by Andrasiu et al.