2

I have seen in several sources (e.g. 1, 2 - page 160), that the complexity of running through an NFA is O(m²n). However I haven't understood why it is so.

My intuition is that the complexity should be O(m^n) (where m is the length of the string, and n is the number of states), because for each letter in the input string, there are n possible states that the NFA can move to them.

Can anyone explain this to me?

Thanks.

Community
  • 1
  • 1
Jadexon
  • 23
  • 5
  • You have to follow all possible paths to get final a state read [Ambiguity in transition: How to process string in NFA?](http://stackoverflow.com/questions/15617429/ambiguity-in-transition-how-to-process-string-in-nfa/15661281#15661281) – Grijesh Chauhan Apr 18 '16 at 09:30
  • @Grijesh Chauhan Thank you for the comment, but I still don't get why it has to be O(m²n)... I'll edit my main question with more explanation about what's my intuition. – Jadexon Apr 18 '16 at 12:46

1 Answers1

0

Let's think about how we'd do one step of simulating the NFA. We begin in some set of active states Qinit. For each state we're in, we look at all the outgoing transitions labeled with the current symbol, then gather them into a set Qmid. Next, we follow all possible ε-transitions from those states and keep repeating this process until there are no more ε-transitions to follow (that is, we find the ε-closure), giving us our new set of state Qnext. We then repeat this process once per character in the input.

So how much time does this take? Well, there are m characters in the input string, so the runtime is m times whatever work we do on one individual character. Each state can have at most n transitions leaving it on each character, so the time to iterate over all the characters in Qinit to find the set Qmid is O(n2): there are O(n) states in Qinit and we only need to scan O(n) transitions per state. From there, we have to keep following ε-transitions until we run out of transitions to follow. We can do that by doing a BFS or DFS starting simultaneously from each state in Qmin and only following ε-transitions. The NFA can have at most O(n2) ε-transitions total (one between each pair of states), so the BFS or DFS will run in time O(n2). Overall we're doing O(n2) work per character, so the total work done is O(mn2).

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • You mention that the time to iterate over all characters is O(n^2) and that the NFA can have at most O(n^2) epsilon transitions total. Does that mean you reduced O(m(n^2 + n^2)) to O(mn^2)? – maddie May 15 '18 at 03:46