patternModerate
Number of words in the regular language $(00)^*$
Viewed 0 times
numberthewordsregularlanguage
Problem
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?
$\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?
Solution
For your language, can you take $p_0(x) = 1/2$, $\lambda_0 = 1$, $p_1(x) = 1/2$, $\lambda_1 = -1$, and $p_i(x) = \lambda_i = 0$ for $i > 1$? The Wikipedia article doesn't say anything about the coefficients being either positive or integral. The sum for my choices is
$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$
which seems to be 1 for even $n$, and 0 for odd $n$. Indeed, a proof by induction seems straightforward.
$\qquad \displaystyle 1/2 + 1/2(-1)^n = 1/2 (1 + (-1)^n)$
which seems to be 1 for even $n$, and 0 for odd $n$. Indeed, a proof by induction seems straightforward.
Context
StackExchange Computer Science Q#1039, answer score: 14
Revisions (0)
No revisions yet.