2
$\begingroup$

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$? Where $a$ is some constant that can depend on $L$.

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.

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ Please do not delete a question once it has been answered. That's rude towards the answerer and to other people who might be interested in the answer. $\endgroup$ – Gilles 'SO- stop being evil' Feb 1 '19 at 12:07
  • 1
    $\begingroup$ Also, it is part of protocol and etiquette to upvote helpful answers and accept the best answer that has answered your question by clicking on the check mark beside the answer. Thanks without upvote or acceptance (which might look like sarcasm) is almost the antithesis of appreciation. $\endgroup$ – John L. Feb 1 '19 at 15:29
2
$\begingroup$

Suppose that the Myhill–Nerode relation of $L$ has the equivalence classes $C_1,\ldots,C_m$. Let $N_i(n) = |C_i \cap \{0,1\}^n|$. If $x,y \in C_i \cap \{0,1\}^n$ then $x^2,y^2 \in \mathbf{S} \subseteq L$, and so $xy,yx \in L$ since $C_i$ is an equivalence class. Therefore $$ |L \cap \{0,1\}^{2n}| \geq \sum_{i=1}^m N_i(n)^2. $$ Since the function $x^2$ is convex, the right-hand side is minimized (under the constraint $\sum_i N_i(n) = 2^n$) when all $N_i(n)$ are equal. Therefore $$ |L \cap \{0,1\}^{2n}| \geq m (2^n/m)^2 = \frac{2^{2n}}{m}. $$

The same argument works if we replace $\mathbf{S}$ with similar languages. Suppose for example that $L$ contains the language of all palindromes $\mathbf{P}$. If $x,y \in C_i \cap \{0,1\}^n$ then $yy^R \in \mathbf{P} \subseteq L$, and so $xy^R \in L$. Just as before, this shows that $|L \cap \{0,1\}^{2n}| \geq 2^{2n}/m$.

Furthermore, for each letter $\sigma \in \{0,1\}$, we have $y\sigma y^R \in L$, and so $x\sigma y^R \in L$. Therefore $$ |L \cap \{0,1\}^{2n+1}| \geq \sum_{i=1}^m 2N_i(n)^2 \geq 2m(2^n/m)^2 = \frac{2^{2n+1}}{m}. $$ In total, we get, for all $n$, $$ |L \cap \{0,1\}^n| \geq \frac{2^n}{m}. $$

Consider now the language $L_k$ of all words in which the first $k$ letters are the same as the last $k$ letters, reversed. This language has $m = \Theta(4^k)$ equivalence classes, contains all large enough palindromes, and has density $1/2^k = \Theta(1/\sqrt{m})$. This suggests the following vague question:

What is the minimal density of a regular language having $m$ equivalence classes and containing all palindromes or all squares?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks for the answer! Hmmm, at this point in the class, we didn't know about the Myhill-Nerode theorem. So the problem is probably solvable without using the theorem right? From the final solution, it looks like you could make an argument based on the number of states in the DFA and even length words. $\endgroup$ – johnny Feb 1 '19 at 6:42
  • $\begingroup$ I’m not terribly interested in tying my hands behind my back. The argument can definitely rephrased in more elementary terms, but I see no reason to. $\endgroup$ – Yuval Filmus Feb 1 '19 at 6:42
  • $\begingroup$ I completely understand.Thanks anyway! $\endgroup$ – johnny Feb 1 '19 at 6:43
  • $\begingroup$ In fact, it's a simple exercise to formulate this in terms of states in a DFA. If you're interested, you should try it out yourself. $\endgroup$ – Yuval Filmus Feb 1 '19 at 14:47
  • 1
    $\begingroup$ The same argument works, since it shows that $xy^R \in L$ for all $x,y \in L$ of the same length. Moreover, you should be able to get that the language is dense for all input lengths. $\endgroup$ – Yuval Filmus Feb 1 '19 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.