- #1

SashaRulez

- 1

- 0

## 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.

Last edited: