Theorem 9.4.2: it is undecidable for 2-DFAs C1 and C2 whether or not L(C1) _ L(C2) = _ (i.e., the empty intersection problem is undecidable for 2-DFAs).
Theorem 9.4.3: for #__, it is undecidable whether or not L(C) = _*•{#} ___*•{#} for 2-NFA C with alphabet ____{#}.
Corollary 9.4.4: the equivalence of 2-NFAs is undecidable.
Previous slide | Back to first slide | View graphic version |