Languages and generating functions

John Howat

We discuss some methods to count the number of words of a given length in a language. We begin by briefly reviewing what a regular language is and what generating functions are. We then show how to construct a generating function for a regular language and show how it can be used to count words. After a few examples, we will show how to perform similar tricks for context-free languages.