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:
“While I do not suggest that humanity will ever be able to dispense with its martyrs, I cannot avoid the suspicion that with a little more thought and a little less belief their number may be substantially reduced.”
—J.B.S. (John Burdon Sanderson)
“I wonder whether mankind could not get along without all these names, which keep increasing every day, and hour, and moment; till at the last the very air will be full of them; and even in a great plain, men will be breathing each other’s breath, owing to the vast multitude of words they use, that consume all the air, just as lamp-burners do gas.”
—Herman Melville (1819–1891)
“It was inspiriting to hear the regular dip of the paddles, as if they were our fins or flippers, and to realize that we were at length fairly embarked. We who had felt strangely as stage-passengers and tavern-lodgers were suddenly naturalized there and presented with the freedom of the lakes and woods.”
—Henry David Thoreau (1817–1862)
“I invented the colors of the vowels!—A black, E white, I red, O blue, U green—I made rules for the form and movement of each consonant, and, and with instinctive rhythms, I flattered myself that I had created a poetic language accessible, some day, to all the senses.”
—Arthur Rimbaud (1854–1891)