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 something tragic about the enormous number of young men there are in England at the present moment who start life with perfect profiles, and end by adopting some useful profession.”
—Oscar Wilde (1854–1900)
“Go to the ant, thou sluggard; consider her ways, and be wise.”
—Bible: Hebrew Proverbs, 6:6.
The words were rendered by Samuel Johnson in the opening lines of The Ant: “Turn on the prudent ant thy heedful eyes, Observe her labours, sluggard, and be wise.”
“The solid and well-defined fir-tops, like sharp and regular spearheads, black against the sky, gave a peculiar, dark, and sombre look to the forest.”
—Henry David Thoreau (1817–1862)
“Experiment is necessary in establishing an academy, but certain principles must apply to this business of art as to any other business which affects the artis tic sense of the community. Great art speaks a language which every intelligent person can understand. The people who call themselves modernists today speak a different language.”
—Robert Menzies (1894–1978)