Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
    Tweeted twitter.com/#!/StackCompSci/status/187704679390658560
4 more precise title
| link

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

3 edited tags, removed redundant part
source | link

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
| link
1
source | link