CHAPTER 2
FINITE AUTOMATA
CHAPTER SUMMARY
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 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.
