I cannot think of a PTIME algorithm to find a rejecting input of an NFA. While it is possible to efficiently find a rejecting input for a DFA, converting an NFA to DFA is too expensive.

The algorithm should have the following behavior: Given an NFA $A = (Q, Sigma, Delta, q_0, F)$, if $L(A) = Sigma^*$, then return the error state $Err$, otherwise return any $w in Sigma^* setminus L(A)$.

Ideally, $w$ should be as short as possible.

Is this possible?

What I tried:

I thought of using a modified version of Thompson’s algorithm. In Thompson’s algorithm, the current input character is used to determine the next set of states from the current set of states. Thompson’s algorithm will reject an input string if (1) the next set of states is empty or (2) if the string ended and the current set of states does not contain a final state.

Let $N_T: P(Q) times Sigma to P(Q)$ be the function from Thompson’s algorithm that given the current set of states and an input character determines the next set of states.

By repeatedly using all characters $c in Sigma$ as input characters to create the next set of states, the algorithm can approximate simulating all input strings. The function determining the next set of states is defined as:

$$N: P(Q) to P(Q); \ N(S) = bigcup_{c in Sigma} N_T(S, c)$$

The current set of states for a given iteration $k$ is defined as: $$S_k =

begin{cases}

{q_0}, & text{if } k = 0 \

N(S_{k-1}), & text{otherwise}

end{cases}

$$

In each iteration $k$, the following conditions (corresponding to the rejection conditions of Thompson’s algorithm) are checked:

- If $exists c in Sigma$ such that $N_T(c)=emptyset$, then all $w in Sigma^k c$ will be rejected by $A$. Return any $w$.
- If $S_k cap F = emptyset$, then all $w in Sigma^k$ will be rejected by $A$. Return any $w$.

Lastly, if an already seen set of states is seen again, the algorithm returns $Err$. This ensures that the algorithm terminates.

However, there are 2 problems with this algorithm:

- It’s only an approximation. There are some NFA for which this algorithm returns $Err$ even though the NFA doesn’t accept all inputs.
- It terminates after at most $2^{O(n)}$ many steps. This isn’t PTIME. However, this problem can be solved by only allowing $|Q|$ many iterations since the shortest rejecting input should have at most $|Q|$ many characters.