O'Reilly logo

An Introduction to Formal Languages and Automata, 6th Edition by Linz

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

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

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