2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.