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.