Chapter 3. Finite State Automata

A language is a subset of the set of strings over an alphabet. In Chapter 2, we have seen how a language can be generated by a grammar. A language can also be recognized by a machine. Such a device is called a recognition device. Hence, a language can have a representation in terms of a generative device as a grammar as well as in terms of a recognition device which is called an acceptor. The simplest machine or recognition device is the finite state automaton which we discuss in this chapter and in the next two chapters. Apart from these two types of representation, there are other representations like regular expressions, which is also discussed in this chapter.

Consider a man watching a TV in his room. The TV ...

Get Introduction to Formal Languages, Automata Theory and Computation now with O’Reilly online learning.

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