### 3.1 DETERMINISTIC FINITE AUTOMATA AND THEIR LANGUAGES

**3.1.0.6 Example.** Consider the restricted URM below that operates over the input alphabet {0, 1}

What does this program do? It has scanned a string of parity 0 (sum of its digits is even) and halted iff it halted while in state 0. This claim will be revisited after we formalize the automaton concept.

#### 3.1.1 The Flow-Diagram Model

The formalization is achieved by first abstracting a command

as the configuration below:

Figure capturing (1) above

Thus the “read” part is implicit, while the labeled arrow that connects the states *L* and *M* denotes exactly the semantics of (1). Therefore, an entire automaton is a *directed graph*—that is, a finite set of (possibly) labeled circles, the *states*, and a finite set of arrows, the *transitions*, the latter labeled by members of the automaton’s input alphabet. The arrows or *edges* interconnect the states. If *L = M*, then we have the configuration

where the optional label could be *L*, or *M*, *L* = *M* (as ...