2.1 DETERMINISTIC FINITE ACCEPTERS
The first type of automaton we study in detail are finite accepters that are deterministic in their operation. We start with a precise formal definition of deterministic accepters.
Figures 1.6 and 1.9 represent two simple automata, with some common features:
- Both have a finite number of internal states.
- Both process an input string, consisting of a sequence of symbols.
- Both make transitions from one state to another, depending on the current state and the current input symbol.
- Both produce some output, but in a slightly different form. The automaton in Figure 1.6 only accepts or rejects the input; the automaton in Figure 1.9 generates an output string.
Notice also that both automata have a single well-defined ...
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.
