NFA equality for automata with partial transition functions and all states accepting

Question

Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in polynomial time whether the two automata recognize the same language? Or is it perhaps PSPACE-hard, like the same problem for general NFAs?

Answer 1

The problem is PSPACE-complete, by reduction from the equivalence problem for NFAs.

Suppose we are given two NFAs $A_1,A_2$ over an alphabet $\Sigma$. Let $\dashv$ be a new symbol. To each of the NFAs we add two new states $q_f,q_t$, and the following transitions:

• An $\epsilon$-transition from the initial state to $q_t$.
• A self-loop on $q_t$ labeled $\Sigma$.
• A transition labeled $\dashv$ from every accepting state to $q_f$.

Let $B_1,B_2$ be the new NFAs, after making all of their states accepting. Then $$ L(B_i) = \Sigma^* \cup (L(A_i)\dashv). $$ Therefore $L(A_1) = L(A_2)$ iff $L(B_1) = L(B_2)$.