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 Oregon [matter] and the annexation of Texas are now all- important to the security and future peace and prosperity of our union, and I hope there are a sufficient number of pure American democrats to carry into effect the annexation of Texas and [extension of] our laws over Oregon. No temporizing policy or all is lost.”
—Andrew Jackson (1767–1845)
“Earthly minds, like mud walls, resist the strongest batteries: and though, perhaps, sometimes the force of a clear argument may make some impression, yet they nevertheless stand firm, and keep out the enemy, truth, that would captivate or disturb them. Tell a man passionately in love, that he is jilted; bring a score of witnesses of the falsehood of his mistress, it is ten to one but three kind words of hers shall invalidate all their testimonies.”
—John Locke (1632–1704)
“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)
“You can’t write about people out of textbooks, and you can’t use jargon. You have to speak clearly and simply and purely in a language that a six-year-old child can understand; and yet have the meanings and the overtones of language, and the implications, that appeal to the highest intelligence.”
—Katherine Anne Porter (1890–1980)