3
$\begingroup$

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:

  1. 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$.
  2. 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:

  1. It's only an approximation. There are some NFA for which this algorithm returns $Err$ even though the NFA doesn't accept all inputs.
  2. It terminates after at most $2^{O(n)}$ many steps. This isn't PTIME.
$\endgroup$
4
$\begingroup$

Keith Ellul, Bryan Krawetz, Jeffrey Shallit and Ming-wei Wang constructed, in their paper Regular Expressions: New Results and Open Problem, a regular expression of size $O(n)$ for which the minimal rejected word has size $\Omega(n2^n)$; here $n$ is an arbitrary parameter. The regular expression can be converted to an NFA with $O(n)$ states and transitions with similar properties.

This shows that you need exponential time just to output $w$.

$\endgroup$
1
  • $\begingroup$ Thank you for the answer! (Page 26 for those searching.) $\endgroup$ Jun 7 '21 at 16:01

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.