ABSTRACT

One of the most intriguing aspects of computer science is the central role that formal

languages play in its theoretical foundation. In this chapter, we describe the structure

of a certain type of such languages. Later, we relate them to computational models-

finite-state automata-that act as “language recognizing machines.” These, together

with generating functions, provide us with powerful counting tools.