USA.: Grand Valley State University (GVSU). - 2014. Mathematics Department. Undergraduate Research. Paper 3, P.p.: 1-12, English.Introduction
A context-free grammar is a mathematical construct that classifies strings (sequences of symbols) as either "valid" or "invalid", by specifying a set of "production rules" which determine the ways in which valid strings can be formed. A "language" (that is, a set of strings) generated by a context-free grammar is known as a context-free language.
Although context-free grammars were initially used to study human language, this paper investigates context-free languages in a more theoretical context. Specifically, we are interested in "counting sequences": given a language, its counting sequence is a sequence of natural numbers stating how many strings of each length are elements of the language.
The ordinary generating function of a sequence is the power series whose coefficients are the elements of the sequence. This paper investigates the properties of ordinary generating functions of counting sequences of context-free languages.
We will begin by de ning a context-free grammar and an ordinary generating function, and discussing some examples. We will then discuss the Chomsky-Schutzenberger Theorem, an important theorem about the generating functions of context-free languages.
Finally, we will extend the notion of a context-free grammar by de ning integer-labeled context-free grammars, where each rule has a (possibly negative) label indicating the multiplicity of that rule. We will prove that an extended version of the Chomsky-Schutzenberger Theorem also holds for integerlabeled context-free grammars.Contents.
1 Introduction.
2 Context-free grammars and their generating functions.
Context-free grammars.
Generating functions for context-free grammars.
Example: a language from Du & Ko.
The Dyck language.
The Chomsky{Schutzenberger Theorem.
Examples from Flajolet.
3 Integer-labeled context-free grammars.
De nitions.
Example from Du & Ko revisited.
The power of nilCFGs? .
Chomsky{Schutzenberger Theorem, extended.
Acknowledgements.
