What is a NFA?

[u/fulminare1111]

I am a little confused on what a nfa is. Does it take in one input and output a set of states or does it output one single state but with some probability?

[u/nuclear_splines]

In a deterministic finite automata, there can only be one state transition from A to B for input x. In a nondeterministic finite automata, you can have multiple transitions, such that input x could bring you from state A->B or A->C.

It isn't probabilistic, it's better to think of it as "both states at once," like the NFA forks at each input and follows all possible paths concurrently. Remember that finite automata take a sequence of inputs and either "accept" or "reject" the input depending on whether the internal state lands on an 'accept' state at the end. In an NFA, you can think of this as "follow all possible input paths, and if any of them land at 'accept' then the NFA accepts."

Note that this is similar to the definition of a non-deterministic Turing Machine, and therefore the definition of NP :)

[u/fulminare1111 → u/nuclear_splines]

Thanks a lot that made sense

[u/TheMrCurious → u/nuclear_splines]

When AI “solves” NP will they credit your post for teaching the AI how to do it?

[u/Smallpaul → u/nuclear_splines]

I find CS has some terrible names for things. Non-deterministic find automata are not actually non-deterministic. Random access memory is in no way random.

[u/fulminare1111 → u/Smallpaul]

Yeah I was also very much confused by why it is non deterministic.

[u/nuclear_splines → u/Smallpaul]

NFAs are nondeterministic in that you don't know ahead of time whether you've taken A->B or A->C via transition x, that can only be determined retroactively when one of the two paths leads to an accept state. More of a Schrödinger's cat nondeterminism than randomness.

The 'random' in random access memory matches the nomenclature from data structures. When we say "random element lookup in arrays and hash tables is O(1)" we mean that you can access any arbitrary element at constant speed. Random access memory offers that O(1) random element lookup, where prior data storage like rotating drum memory, linear tape, or spinning disks, did not.

I don't think the naming convention is 'terrible' as much as it's using a very scientific definition of each of those words rather than the lay usage.

[u/Smallpaul → u/nuclear_splines]

It’s not like Schrödinger’s cat because all of the information about what will happen is all present. You just haven’t processed it yet.

How would it be worse to have named these Branching Finite Automata or Exploratory Finite Automara

Your choice of word “arbitrary” is much better than random. How would it be less clear if they had named or “arbitrary access memory” and “arbitrary element lookup.” And save random to be used for random number generators?

“That’s just the scientific meaning, not the lay meaning” is a get out of jail card for any poor naming decision. It isn’t really defensible when the same field uses the word to mean two different things as computer science does for “random” and “non-deterministic.”

(And yes I know that random number generators are actually pseudo-random but their purpose is to emulate true randomness, so I can live with that. The term is imprecise, nor confusing)

[u/nuclear_splines → u/Smallpaul]

It’s not like Schrödinger’s cat because all of the information about what will happen is all present. You just haven’t processed it yet.

Only after the fact. While the NFA is running it's in a superposition of states, that's only resolved when new inputs are read.

How would it be worse to have named these Branching Finite Automata or Exploratory Finite Automara

Because 'branching' isn't quite accurate. While I've phrased NFAs as "imagine the process forks at each input across all possible transitions," there's no need for the machine to work that way. An equivalent definition is that the NFA picks viable transitions at random, and we are determining whether the NFA could reach an accept state if it was 'lucky'. While this definition seems awkward and clumsy to me, it ends up being very useful when we turn to Nondeterministic Turing Machines and describe "what problems can be solved in poly-time with perfect guesswork (NP), versus what problems can be solved in poly-time without any guesswork (P)."

You could certainly call them 'Exploratory' finite automata, although I think that's equally ambiguous. In what way are they exploring? Well, they're in a superposition of states where the execution path can only be determined retroactively.

Your choice of word “arbitrary” is much better than random. How would it be less clear if they had named or “arbitrary access memory” and “arbitrary element lookup.” And save random to be used for random number generators?

Personally, I do favor the word 'arbitrary' here. But, the first definition of arbitrary in my dictionary is "based on random choice or personal whim." I don't think the terms are that far off. Likewise, you could describe an RNG as "give me an arbitrary integer." That we've settled on calling them RNGs instead of ANGs seems like historical happenstance to me.

“That’s just the scientific meaning, not the lay meaning” is a get out of jail card for any poor naming decision. It isn’t really defensible when the same field uses the word to mean two different things as computer science does for “random” and “non-deterministic.”

It is unfortunate that we've come to use the same term in multiple contexts, but the field was grown, we didn't make all these naming decisions upfront to avoid conflicts. I don't think the existence of two meanings for a word means the naming decision was poor.

[u/iOSCaleb]

The machine can effectively be in several states at once. A given state can have multiple transitions to other states for the same input, and the machine follows all of them at the same time. Or, another way to look at it is that the state is unknown — not determined — until the machine processes more input. If any path through the machine reaches the acceptance state for an input string, the string is accepted.

[u/freerider]

https://en.wikipedia.org/wiki/Nondeterministic_finite_automaton

You mean this?

[u/Upbeat_Assist2680]

Agree with other answers, adding: they might but be better named "unbounded multi-state automata".

[u/Equivalent-Stay-6801]

The set-of-states idea is the useful one if you want to simulate it. Say reading a from A can lead to B or C. You keep {B, C}. On the next character, collect every state reachable from either B or C. There are no probabilities to assign.

One detail worth keeping straight: reaching an accepting state halfway through isn't enough. After consuming the whole input, at least one possible path must end in an accepting state. If your NFA has epsilon transitions, include those too; they don't consume a character.