Question - What Is The Concept Of Nondeterministic Finite Automaton (nfa) ?
Answer -
Nondeterminism plays a key role in the theory of computing. A nondeterministic finite state automaton is one in which the current state of the machine and the current input do not uniquely determine the next state. This just means that a number of subsequent states (zero or more) are possible next states of the automaton at every step of a computation. Of course, nondeterminism is not realistic, because in real life, computers must be deterministic. Still, we can simulate nondeterminism with deterministic programs. Furthermore, as a mathematical tool for understanding computability, nondeterminism is invaluable.
As with deterministic finite state automata, a nondeterministic finite state automaton has five components.
- a set of states
- a finite input alphabet from which input strings can be constructed
- a transition function that describes how the automaton changes states as it processes an input string
- a single designated starting state
- a set of accepting states
The only difference lies in the transition function, which can now target subsets of the states of the automaton rather than a single next state for each state, input pair.