Question 27

Evaluate Problem I: 'Given NFAs $N_1$ and $N_2$, is $L(N_1) \cap L(N_2) = \emptyset$?'
Regular languages are closed under intersection. We can construct a cross-product automaton $N$ recognizing $L(N_1) \cap L(N_2)$ and check whether any accept state is reachable from the start state using breadth-first search or depth-first search in polynomial time. Hence, Problem I is DECIDABLE.

Evaluate Problem II: 'Given a CFG $G$ and a string $x$, does $x \in L(G)$?'
This is the CFG membership problem. It can be solved in $O(|x|^3)$ time using the Cocke-Younger-Kasami (CYK) dynamic programming algorithm or Earley's parser. Hence, Problem II is DECIDABLE.

Evaluate Problem III: 'Given CFGs $G_1$ and $G_2$, is $L(G_1) = L(G_2)$?'
Equivalence of context-free languages is a well-known undecidable problem (proven by reduction from the Post Correspondence Problem or CFG universality $L(G) = \Sigma^*$). Hence, Problem III is UNDECIDABLE.

Evaluate Problem IV: 'Given a TM $M$, is $L(M) = \emptyset$?'
Emptiness of a recursively enumerable language is undecidable by Rice's Theorem, as emptiness is a non-trivial semantic property of Turing machine languages. Hence, Problem IV is UNDECIDABLE.

Therefore, problems III and IV only are undecidable.