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:
“There is not to be found, in all history, any miracle attested by a sufficient number of men, of such unquestioned good sense, education, and learning, as to secure us against all delusion in themselves ... beyond all suspicion of any design to deceive others ... and at the same time attesting facts, performed in such a public manner, and in so celebrated a part of the world, as to render the detection unavoidable.”
—David Hume (1711–1776)
“How often you, spurned, will run to my door, when your strong words shall have fallen into a sob, and a trembling horror will begin from your sad tears.”
—Propertius Sextus (c. 50–16 B.C.)
“A regular council was held with the Indians, who had come in on their ponies, and speeches were made on both sides through an interpreter, quite in the described mode,—the Indians, as usual, having the advantage in point of truth and earnestness, and therefore of eloquence. The most prominent chief was named Little Crow. They were quite dissatisfied with the white man’s treatment of them, and probably have reason to be so.”
—Henry David Thoreau (1817–1862)
“The writer’s language is to some degree the product of his own action; he is both the historian and the agent of his own language.”
—Paul De Man (1919–1983)