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:
“I will not adopt that ungenerous and impolitic custom so common with novel writers, of degrading by their contemptuous censure the very performances, to the number of which they are themselves adding—joining with their greatest enemies in bestowing the harshest epithets on such works, and scarcely ever permitting them to be read by their own heroine, who, if she accidentally take up a novel, is sure to turn over its insipid leaves with disgust.”
—Jane Austen (1775–1817)
“It is never the thing but the version of the thing:
The fragrance of the woman not her self,
Her self in her manner not the solid block,
The day in its color not perpending time,
Time in its weather, our most sovereign lord,
The weather in words and words in sounds of sound.”
—Wallace Stevens (1879–1955)
“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)
“Our language has wisely sensed these two sides of man’s being alone. It has created the word “loneliness” to express the pain of being alone. And it has created the word “solitude” to express the glory of being alone. Although, in daily life, we do not always distinguish these words, we should do so consistently and thus deepen our understanding of our human predicament.”
—Paul Tillich (1886–1965)