HW5
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
