How many words of length n are there in this regular language?

[SashaRulez]

Homework Statement

I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.Suppose we have a regular language $L \subseteq \{0,1\}^*$ and the language $\mathbf{S} = \{uu: u\in \{0,1\}^*\}$ is a subset of $L$. Clearly for even $n$ there are at least $2^{n/2}$ words of length $n$ in $L$. How would I show that there are at least $a2^n$ length $n$ binary words in $L$, for infinitely many $n$, without using the Myhill-Nerode theorem? Where $a$ is some constant that can depend on $L$.

The Attempt at a Solution

Clearly $\mathbf{S}$ is non-regular, so there must be more length $n$ words accepted, but I am not sure how to get $\Theta(2^n)$ length $n$ words. Somehow one has to use the regularity of $L$, so maybe take its finite automaton, and relate the number of words to states/transitions? I don't see a way to proceed.

 

[jbriggs444]

Homework Statement

I am self studying automata theory and I found a problem set from an old class I took a few years ago, but I have no clue how to solve the following problem, any help would be appreciated.Suppose we have a regular language $L \subseteq \{0,1\}^*$ and the language $\mathbf{S} = \{uu: u\in \{0,1\}^*\}$ is a subset of $L$. Clearly for even $n$ there are at least $2^{n/2}$ words of length $n$ in $L$.

Wait. L is a subset of $\{0,1\}^*$, not necessarily equal to the whole thing. For all we know, L could be the empty language. Similarly, S could be the empty language. There need be no more than zero words of length n for any given n.

Regardless of n, 0 < 2^n and it would seem that the obvious claim is falsified.

There is an obvious choice of "a" that makes for an easy solution to the problem as stated.