Def. An unrestricted grammar G = (V,T,R,S)

Def. An unrestricted grammar G = (V,T,R,S) is said to be a context-free grammar (CFG) if every production u à v in R is of the form A à v where A is an element of V.

Q1 - Using PCP show that for two CFG’s G1 and G2 the problem whether L(G1) and L(G2) are disjoint sets is undecidable.

Q2 - For an unrestricted grammar G show that whether some wÎ L(G) is an undecidable problem.

Main text 4.6.3, 5.7.4 (Explain/interpret difference of these two problems/solutions) 5.7.5