Informal Introduction
An NFA, similar to a DFA, consumes a string of input symbols. For each input symbol, it transitions to a new state until all input symbols have been consumed. Unlike a DFA, it is non-deterministic, i.e., for any input symbol the next state may be any one of several possible states. Thus, in the formal definition, the next state is an element of the power set of the states, which is a set of states to be considered at once. The notion of accepting an input is similar to that for the DFA. When the last input symbol is consumed, the NFA accepts if and only if there is some set of transitions that will take it to an accepting state. Equivalently, it rejects, if, no matter what transitions are applied, it would not end in an accepting state.
Read more about this topic: Nondeterministic Finite Automaton
Famous quotes containing the words informal and/or introduction:
“We are now a nation of people in daily contact with strangers. Thanks to mass transportation, school administrators and teachers often live many miles from the neighborhood schoolhouse. They are no longer in daily informal contact with parents, ministers, and other institution leaders . . . [and are] no longer a natural extension of parental authority.”
—James P. Comer (20th century)
“Do you suppose I could buy back my introduction to you?”
—S.J. Perelman, U.S. screenwriter, Arthur Sheekman, Will Johnstone, and Norman Z. McLeod. Groucho Marx, Monkey Business, a wisecrack made to his fellow stowaway Chico Marx (1931)