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 two great points of difference between a democracy and a republic are: first, the delegation of the government, in the latter, to a small number of citizens elected by the rest; secondly, the greater number of citizens and greater sphere of country over which the latter may be extended.”
—James Madison (1751–1836)
“The bitterest tears shed over graves are for words left unsaid and deeds left undone.”
—Harriet Beecher Stowe (1811–1896)
“This is the frost coming out of the ground; this is Spring. It precedes the green and flowery spring, as mythology precedes regular poetry. I know of nothing more purgative of winter fumes and indigestions. It convinces me that Earth is still in her swaddling-clothes, and stretches forth baby fingers on every side.”
—Henry David Thoreau (1817–1862)
“A president, however, must stand somewhat apart, as all great presidents have known instinctively. Then the language which has the power to survive its own utterance is the most likely to move those to whom it is immediately spoken.”
—J.R. Pole (b. 1922)