The Number of Words in A Regular Language
Let denote the number of words of length in . The ordinary generating function for L is the formal power series
The generating function of a language L is a rational function if and only if L is regular. Hence for any infinite regular language there exist constants and polynomials such that for every the number of words of length in satisfies the equation .
Thus, non-regularity of certain infinite languages can be proved by counting the words of a given length in . Consider, for example, the Dyck language of strings of balanced parentheses. The number of words of length in the Dyck language is equal to the Catalan number, which is not of the form, witnessing the non-regularity of the Dyck language.
The zeta function of a language L is
The zeta function of a regular language is not in general rational, but that of a cyclic language is.
Read more about this topic: Regular Language
Famous quotes containing the words number, words, regular and/or language:
“The poetic act consists of suddenly seeing that an idea splits up into a number of equal motifs and of grouping them; they rhyme.”
—Stéphane Mallarmé (1842–1898)
“As societies grow decadent, the language grows decadent, too. Words are used to disguise, not to illuminate, action: you liberate a city by destroying it. Words are to confuse, so that at election time people will solemnly vote against their own interests.”
—Gore Vidal (b. 1925)
“[I]n our country economy, letter writing is an hors d’oeuvre. It is no part of the regular routine of the day.”
—Thomas Jefferson (1743–1826)
“This poem is concerned with language on a very plain level.
Look at it talking to you.”
—John Ashbery (b. 1927)