Theorem 9.3.6: it is undecidable for an arbitrary context-free grammar G if L(G) = _*.
Corollary 9.3.7: it is undecidable for arbitrary context-free grammars G1 and G2 whether or not L(G1) = L(G2).
Theorem 9.4.1: it is undecidable for DGSMs M1 and M2 whether or not there exists x__+ so that M1(x) = M2(x).
Previous slide | Next slide | Back to first slide | View graphic version |