Generating function of Language is rational

94 Views Asked by At

Let W be the set of all words over an alphabet $\Sigma$. Let $$L=\{w\in\Sigma^* | w\neq uvu',\text{ with }u,u'\in\Sigma^*,v\in W\}$$

I have to show that the generating function of L is rational.

My first problem is to understand the language. I think this language contain nor words !

Thank you for your help

1

There are 1 best solutions below

5
On

Yes, $L=\varnothing$. Thus, if $\ell(n)$ is the number of words of $L$ of length $n$, we have $\ell(n)=0$ for all $n\in\Bbb N$. Is this function $\ell$ a rational function?