# Return to Question

Tweeted twitter.com/#!/StackCompSci/status/187704679390658560
4 more precise title

# Question about the number Number of words in athe regular language $(00)^*$

3 edited tags, removed redundant part

According to Wikipedia, for any regular language $$L$$ there exist constants $$\lambda_1,\ldots,\lambda_k$$ and polynomials $$p_1(x),\ldots,p_k(x)$$ such that for every $$n$$ the number $$s_L(n)$$ of words of length $$n$$ in $$L$$ satisfies the equation $$s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$$

$$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$$.

The language $$L =\{ 0^{2n} \mid n \in\mathbb{N} \}$$ is regular ($$(00)^*$$ matches it). $$s_L(n) = 1$$ iff n is even, and $$s_L(n) = 0$$ otherwise. According to the above, there has to be constants $$\lambda_1,\ldots,\lambda_k$$ and polynomials $$p_1(x),\ldots,p_k(x)$$ such that $$s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$$.

However, I can'tcan not find themthe $$\lambda_i$$ and $$p_i$$ (that have to exist by the above). As $$s_L(n)$$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of themsummands like in a Taylor expansion. Can anyone enlighten me?

According to Wikipedia, for any regular language $$L$$ there exist constants $$\lambda_1,\ldots,\lambda_k$$ and polynomials $$p_1(x),\ldots,p_k(x)$$ such that for every $$n$$ the number $$s_L(n)$$ of words of length $$n$$ in $$L$$ satisfies the equation $$s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$$.

The language $$L =\{ 0^{2n} \mid n \in\mathbb{N} \}$$ is regular ($$(00)^*$$ matches it). $$s_L(n) = 1$$ iff n is even, and $$s_L(n) = 0$$ otherwise. According to the above, there has to be constants $$\lambda_1,\ldots,\lambda_k$$ and polynomials $$p_1(x),\ldots,p_k(x)$$ such that $$s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$$.

However, I can't find them. As $$s_L(n)$$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of them like a Taylor expansion. Can anyone enlighten me?

According to Wikipedia, for any regular language $$L$$ there exist constants $$\lambda_1,\ldots,\lambda_k$$ and polynomials $$p_1(x),\ldots,p_k(x)$$ such that for every $$n$$ the number $$s_L(n)$$ of words of length $$n$$ in $$L$$ satisfies the equation

$$\qquad \displaystyle s_L(n)=p_1(n)\lambda_1^n+\dots+p_k(n)\lambda_k^n$$.

The language $$L =\{ 0^{2n} \mid n \in\mathbb{N} \}$$ is regular ($$(00)^*$$ matches it). $$s_L(n) = 1$$ iff n is even, and $$s_L(n) = 0$$ otherwise.

However, I can not find the $$\lambda_i$$ and $$p_i$$ (that have to exist by the above). As $$s_L(n)$$ has to be differentiable and is not constant, it must somehow behave like a wave, and I can't see how you can possibly do that with polynomials and exponential functions without ending up with an infinite number of summands like in a Taylor expansion. Can anyone enlighten me?

2 edited tags
1