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 rising power of the United States in world affairs ... requires, not a more compliant press, but a relentless barrage of facts and criticism.... Our job in this age, as I see it, is not to serve as cheerleaders for our side in the present world struggle but to help the largest possible number of people to see the realities of the changing and convulsive world in which American policy must operate.”
—James Reston (b. 1909)
“Nor for my words shall ye forget your tears,
Or hope again for aught that I can say,
The idle singer of an empty day.”
—William Morris (1834–1896)
“They were regular in being gay, they learned little things that are things in being gay, they learned many little things that are things in being gay, they were gay every day, they were regular, they were gay, they were gay the same length of time every day, they were gay, they were quite regularly gay.”
—Gertrude Stein (1874–1946)
“Poetry is the universal language which the heart holds with nature and itself. He who has a contempt for poetry, cannot have much respect for himself, or for anything else.”
—William Hazlitt (1778–1830)