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