A finite state machine that may have multiple possible transitions, or none, for a given state and input symbol, and is said to accept an input if any sequence of choices leads to an accepting state; equivalent in recognizing power to a deterministic finite automaton but often more compact to describe.
Facts
Core PrincipleAn input is accepted if there exists at least one sequence of choices leading to an accepting state after the whole input is consumed. 1 Connections
Sources
1. Nondeterministic finite automaton - Wikipedia
Opening paragraph, sentence on Rabin and Scott
NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs.
Informal introduction
If there exists at least one "lucky run", i.e. some sequence of choices leading to an accepting state after completely consuming the input, it is accepted.
In Group: Models of Computation and Automata, Lead
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if each of its transitions is uniquely determined by its source state and input symbol, and reading an input symbol is required for each state transition.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.