O'Reilly logo

Theory of Computation by George Tourlakis

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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}

Images

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. Images

3.1.1   The Flow-Diagram Model

The formalization is achieved by first abstracting a command

Images

as the configuration below:

Images

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

Images

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required