2.2 NONDETERMINISTIC FINITE ACCEPTERS
If you examine the automata we have seen so far, you will notice a common feature: a unique transition is defined for each state and each input symbol. In the formal definition, this is expressed by saying that δ is a total function. This is the reason we call these automata deterministic. We now complicate matters by giving some automata choices in some situations where more than one transition is possible. We will call such automata nondeterministic.
Nondeterminism is, at first sight, an unusual idea. Computers are deterministic machines, and the element of choice seems out of place. Nevertheless, nondeterminism is a useful concept, as we will see.
Definition of a Nondeterministic Accepter
Nondeterminism ...
Get An Introduction to Formal Languages and Automata, 7th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
