[uryga]

the "nondeterminism" here doesn't mean we're dealing with probabilities, it's a more discrete kind - it just means that instead of

  S1 --a--> S2

you can have

  S1 --a--> S2
    '--a--> S3
    '--a--> S4

i.e. transition to multiple states "at once"¹. then, instead of being in one state, like an FSM, your NFA is in a set of states, like it had multiple threads, and proceeds "in parallel" from each state. probably not the best explanation, but i'm sure you can find good material about this.

---

¹ this a way to represent nondeterminism in a pure/math-y setting: instead of

  def f():
    b = random_bool()
    if b:
      res = "yes"
    else:
      res = "no"
    return res

you do

  def random_bool2():
    return {True, False}

  def f2():
    res = set()
    for b in random_bool2():
      if b:
        res.add("yes")
      else:
        res.add("no")
    return res

or just:

  def f2():
    return {"yes", "no"}

i.e enumerate all the possible results f() could give depending on what `random_bool()` returns.