Editing Regular language (section)

== Number of words in a regular language ==
Let <math>s_L(n)</math> denote the number of words of length <math>n</math> in <math>L</math>.  The [[ordinary generating function]] for ''L'' is the [[formal power series]]
: <math>S_L(z) = \sum_{n \ge 0} s_L(n) z^n \ . </math>

The generating function of a language ''L'' is a [[rational function]] if ''L'' is regular.<ref name=Honkala>{{cite journal | zbl=0675.68034 | last=Honkala | first=Juha | title=A necessary condition for the rationality of the zeta function of a regular language | journal=Theor. Comput. Sci. | volume=66 | issue=3 | pages=341–347 | year=1989 | doi=10.1016/0304-3975(89)90159-x | doi-access=free }}</ref>  Hence for every regular language <math>L</math> the sequence <math>s_L(n)_{n \geq 0}</math> is [[constant-recursive sequence|constant-recursive]]; that is, there exist an [[integer]] constant <math>n_0</math>, [[complex number|complex]] constants <math>\lambda_1,\,\ldots,\,\lambda_k</math> and complex [[polynomial]]s <math>p_1(x),\,\ldots,\,p_k(x)</math> such that for every <math>n \geq n_0</math> the number <math>s_L(n)</math> of words of length <math>n</math> in <math>L</math> is <math>s_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n</math>.<ref>Flajolet & Sedgweick, section V.3.1, equation (13).</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1048 |title=Number of words in the regular language $(00)^*$|website=cs.stackexchange.com|access-date=10 April 2018}}</ref><ref>{{cite web| url = https://cs.stackexchange.com/q/11333| title = Proof of theorem for arbitrary DFAs}}</ref><ref>{{cite web|url=https://cs.stackexchange.com/q/1045 |title=Number of words of a given length in a regular language|website=cs.stackexchange.com|access-date=10 April 2018}}</ref>

Thus, non-regularity of certain languages <math>L'</math> can be proved by counting the words of a given length in
<math>L'</math>. Consider, for example, the [[Dyck language]] of strings of balanced parentheses. The number of words of length <math>2n</math>
in the Dyck language is equal to the [[Catalan number]] <math>C_n\sim\frac{4^n}{n^{3/2}\sqrt{\pi}}</math>, which is not of the form <math>p(n)\lambda^n</math>,
witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvalues <math>\lambda_i</math> could have the same magnitude. For example, the number of words of length <math>n</math> in the language of all even binary words is not of the form <math>p(n)\lambda^n</math>, but the number of words of even or odd length are of this form; the corresponding eigenvalues are <math>2,-2</math>. In general, for every regular language there exists a constant <math>d</math> such that for all <math>a</math>, the number of words of length <math>dm+a</math> is asymptotically <math>C_a m^{p_a} \lambda_a^m</math>.<ref>Flajolet & Sedgewick (2002) Theorem V.3</ref>

The ''zeta function'' of a language ''L'' is<ref name=Honkala/>
: <math>\zeta_L(z) = \exp \left({ \sum_{n \ge 0} s_L(n) \frac{z^n}{n} }\right) . </math>

The zeta function of a regular language is not in general rational, but that of an arbitrary [[cyclic language]] is.<ref>{{cite journal | zbl=0797.68092 | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Zeta functions of formal languages | journal=Trans. Am. Math. Soc. | volume=321 | number=2 | pages=533–546 | year=1990 | doi=10.1090/s0002-9947-1990-0998123-x| citeseerx=10.1.1.309.3005 }}</ref><ref>Berstel & Reutenauer (2011) p.222</ref>