Theorem 9.3.2: it is undecidable for homomorphisms h1,h2: _* ___* whether or not there exists x__+ so that h1(x) = h2(x).
Theorem 9.3.3: it is undecidable whether or not an arbitrary context-free grammar is ambiguous.
Corollary 9.3.4: it is undecidable if the intersection of the languages of two arbitrary context-free grammars is empty.
Corollary 9.3.5: it is undecidable for an arbitrary context-sensitive grammar G whether or not L(G) = _.
Previous slide | Next slide | Back to first slide | View graphic version |