2
$\begingroup$

I am interested in testing for a given string (w) whether it is in the language (L) defined by a nondeterministic finite automaton (A). I have some blurry point in my mind.

What is the complexity of this test by using the NFA and backtracking? Assume my NFA has m states and string (w) has length n (|w| = n). For regular expressions, by using Thompson's algorithm, the resultant NFA has the same complexity (worst case) if I use backtracking?

What are the methods/algorithms other than backtracking and converting to DFA?

$\endgroup$
  • 1
    $\begingroup$ The most efficient way is described in the comments and hinty answer to this question. Your other questions can't really be answered because you're asking about the computational complexity of some variant of "Does this automaton accept this string?", which you haven't precisely defined. Is the automaton part of the input? Or is there a fixed automaton and you want to know if it accepts a string given as input to the problem? $\endgroup$ – David Richerby Dec 1 '14 at 8:18
  • $\begingroup$ Thank you David. However for different methods there is a worst case scenario which specify a bounded upper limit for the given method. For example, backtracking has a complexity of $O(2^n)$ I think. This is not related to your automaton? $\endgroup$ – Deniz Dec 1 '14 at 8:32
  • $\begingroup$ I'm not sure what you mean by "for different methods there is a worst case scenario which specify a bounded upper limit for the given method." $\endgroup$ – David Richerby Dec 1 '14 at 8:37
  • $\begingroup$ I think I am talking about alternative NFA simulation algorithms like dynamic programming. May be I used some terms in the wrong place, not sure. Please refer to the comments link here for this answer. $\endgroup$ – Deniz Dec 1 '14 at 15:55
2
$\begingroup$

A naïve backtracking algorithm will still result in exponential behaviour ($O(2^{n})$ where $n$ is the length of the input string). This behaviour can occur even with very small automata (i.e. where the number of states $m$ is a fixed constant).

Consider for example the NFA $M$ below:

NFA which can has exponential worst case backtracking behaviour.

The alphabet is simply $\Sigma =\{0\}$, and the language is $L(M) = \{0^{k}\mid k \in \mathbb{N}\} = \Sigma^{\ast}$. If our algorithm chooses poorly for even the first step (for example if we use the obvious choice and go by state ID), then we're stuck between $q_{0}$ and $q_{1}$, where at each point in the input, we have the choice of moving to the opposite state, or staying where we are - i.e. a binary choice for each character, for the entire length of the string, giving $2^{n}$ steps before we manage to backtrack to $q_{2}$ and then move along the correct path to $q_{4}$.

So even with only 4 states and where every string is valid, we can still get terrible performance from a backtracking approach.

There is a much better approach however. Even without converting the NFA to a DFA we can decide acceptance in polynomial time. As we are dealing with a regular language, we don't need to remember the entire computation history up to this point (which is what backtracking does), we only need to know what state we are up to at the current point. In a DFA this is very easy, as we can only be in one state at any point, but an NFA (without knowing the final computation path) allows more possibilities. However we can simply keep track of these possibilities. The algorithm is as follows:

  1. Initialise $S_{0}$ to $\{s_{0}\}$ where $s_{0}$ is the start state.

  2. For each symbol of the input $c_{i}$ with $1 \leq i \leq n$, for each state $s \in S_{i-1}$, let $E(s,c_{i})$ be the set of states reachable from $s$ using $c_{i}$ and any number of $\varepsilon$-moves1. Set $C_{i} = C_{i} \cup E(s,c_{i})$.

  3. If there is an accepting state in the set $C_{n}$, return $\mathrm{YES}$, otherwise return $\mathrm{NO}$.

So all the algorithm is really doing is keeping track of all the states we could be up to after having read $k$ symbols from the input.

Assuming that the NFA is fixed, this algorithm is $O(n)$-time in the length of the input string. If the NFA is part of the input, it's a little more complicated, but still polynomial time - $O(m^{2}n)$ where $m$ is the number of states (if I haven't missed an implicit loop in there).

Footnotes.

  1. That is, we take the $\varepsilon$-closure of the state $s$, then from each of these states see if we can move using symbol $c_{i}$, then for those where we can, we take the $\varepsilon$-closure again, and this gives us $E(s,c_{i})$.
$\endgroup$
  • $\begingroup$ Thank you Luke. However, I have questions in order to clarify your reply in my mind. You said complexity is $O(2^n)$, but is it the same for all cases? For example, add a new state $q_3$ and modify the automaton like the one here In that case, we have $q_3$ in addition to the $q_0$ and $q_1$ and as far as I understood we have $3^n$ possible path that we can try before backtracking to $q_4$. Therefore, the complexity goes to $O(m^n)$ where $m$ is the number of states (3 in that case). Am I right or missing something? $\endgroup$ – Deniz Dec 3 '14 at 9:42
  • $\begingroup$ Your explanation is quite good and I am trying to learn more from your reply. Another question is for the method you mentioned to test the string in polynomial time $Q(m^2n)$. I think we can go to $m$ states from one state (for the current input) and for the next input we could have $m$ states for each state we find for the previous input. That's where $m^2$ comes from and we repeat this step for each of the input character so we have $n * m^2$ totally. Is it right? $\endgroup$ – Deniz Dec 3 '14 at 10:01
  • $\begingroup$ @Deniz, you are correct in both cases. Different NFAs might give different complexity, and $O(m^{n})$ can be 'achieved' in the way you describe. Secondly, that is indeed where the $m^{2}\times n$ comes from. $\endgroup$ – Luke Mathieson Dec 4 '14 at 11:32

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.