  In this chapter we discuss the problem of enumerating distinct regular
expressions by size and the regular languages they represent. We discuss
various notions of the size of a regular expression that appear in the
literature and their advantages and disadvantages. We consider a formal
definition of regular expressions using a context-free grammar.
  We then show how to enumerate strings generated by an unambiguous
context-free grammar using the Chomsky-Sch\"utzenberger theorem. This theorem
allows one to construct an algebraic equation whose power series expansion
provides the enumeration. Classical tools from complex analysis, such as
singularity analysis, can then be used to determine the asymptotic behavior of
the enumeration.
  We use these algebraic and analytic methods to obtain asymptotic estimates on
the number of regular expressions of size n. A single regular language can
often be described by several regular expressions, and we estimate the number
of distinct languages denoted by regular expressions of size n. We also give
asymptotic estimates for these quantities. For the first few values, we provide
exact enumeration results.
