Given a finite language $L$ with $|L|$ number of elements, what is $|L^i|$ (the language $L$ concatenated with itself $i$ times)? If there is no exact result, is there an upper/lower bound?

Define concatenation of $L$ with itself to be as the classical definition: $LL = \{wx \space | \space w,x \in L\}$. Similarly, $L^n = \{a_1a_2...a_n \space | \space a_i \in L, \forall i \in [1, n] \}$.

Clearly, a non-tight upper bound is $|L|^i$ (each element in concatenation is unique) given that $|L| > 1$, but I would like to know if there is either a tight upper bound or tight lower bound.

  • 6
    $\begingroup$ The upper bound $|L|^i$ is obviously tight (it is attained e.g. if all words in $L$ have the same length). On the other hand, $|L^i|$ may be as low as $i(|L|-1)+1$ (e.g., if $L=\{a^j:j=1,\dots,|L|\}$). $\endgroup$ Oct 1 '14 at 18:51
  • $\begingroup$ Thanks on the first one. For the lower bound, is that attained when all the words have the same length? $\endgroup$
    – Ryan
    Oct 1 '14 at 18:59
  • 1
    $\begingroup$ No. The upper bound is attained when all words have the same length. $\endgroup$ Oct 1 '14 at 19:01
  • $\begingroup$ @EmilJeřábek oh duh, you're right. $\endgroup$
    – Ryan
    Oct 1 '14 at 19:50

You can show $ |L|^i $ is a tight upper bound by using the following language:

$ L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}. $

Any concatenation gives a new string. For a lower bound, I can suggest the following unary language:

$ U = \{a,aa,aaa,\ldots,a^k \mid k \geq 1 \} $.

Then, $ U^i = \{ a^i,a^{i+1},\ldots,a^{ki} \} $ and so $ |U^i| = i|U|-i+1 $.

Emil's (Jerabek) comment appeared during writing my answer and so before posting my answer.

  • $\begingroup$ Seeing as we made independently the same guess, I wonder whether the lower bound is optimal. $\endgroup$ Oct 1 '14 at 20:11
  • $\begingroup$ It seems to be optimal to me. $\endgroup$
    – Ryan
    Oct 1 '14 at 20:54
  • 5
    $\begingroup$ Ah, yes, and more generally, if $L_0$ and $L_1$ are nonempty, then $|L_0L_1|\ge|L_0|+|L_1|-1$. Assume wlog $|L_0|\le|L_1|$, let $a\in L_0$ be of maximal length, and $b\in L_1$ of minimal length. Then $aL_1\cup L_0b\subseteq L_0L_1$ contains $|L_0|+|L_1|-1$ distinct words, unless there is $a\ne a'\in L_0$ of the same length as $a$, in which case $\{a,a'\}L_1$ are $2|L_1|\ge|L_0|+|L_1|$ distinct words. $\endgroup$ Oct 1 '14 at 21:37

If $L$ is any finite code (that is, if $L^*$ is a free monoid of basis $L$), then $|L^i| = |L|^i$. This is the case in particular if $L$ is a prefix code: no word of $L$ is a proper prefix of another word of $L$.

The lower bound is $i|L| - i$ (a slight improvement over the suggested $i|L| - i + 1$). It is obtained for $L = \{1, a, a^2, \ldots, a^{k-1}\}$.

EDIT. As pointed out by Emil Jeřábek, I miscounted the size of $\{1, a, a^2, \ldots, a^{k-1}\}$ and the lower bound is indeed $i|L| - i + 1$.

  • 2
    $\begingroup$ You have miscounted the size of $\{a^j:j=0,\dots,i(k-1)\}$. The tight $i|L|-i+1$ lower bound is proved in my comment to Abuzer Yakaryilmaz’s answer. $\endgroup$ Oct 5 '14 at 11:25

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.