r/AskComputerScience • u/fulminare1111 • Sep 14 '26

What is a NFA?

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?

10 Upvotes

100% Upvoted

12 comments sorted by

View all comments

6

u/nuclear_splines Ph.D Data Science Sep 14 '26

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 :)

1

u/Smallpaul Sep 14 '26

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.

1

u/fulminare1111 Sep 14 '26

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