In this chapter, we encounter our first simple automaton, a finite state accepter. It is finite because it has only a finite set of internal states and no other memory. It is called an accepter because it processes strings and either accepts or rejects them, so we can think of it as a simple pattern recognition mechanism.

We start with a deterministic finite accepter, or dfa. The adjective “deterministic” signifies that the automaton has one and only one option at any time. We use dfa’s to define a certain type of language, called a regular language, and so establish a first connection between automata and languages, a recurring theme in subsequent discussions. Next, we introduce nondeterministic automata, ...

Get An Introduction to Formal Languages and Automata, 6th Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.