5
$\begingroup$

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.

$\endgroup$
4
  • 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, 2014 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$ Oct 1, 2014 at 18:59
  • 1
    $\begingroup$ No. The upper bound is attained when all words have the same length. $\endgroup$ Oct 1, 2014 at 19:01
  • $\begingroup$ @EmilJeřábek oh duh, you're right. $\endgroup$ Oct 1, 2014 at 19:50

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Seeing as we made independently the same guess, I wonder whether the lower bound is optimal. $\endgroup$ Oct 1, 2014 at 20:11
  • $\begingroup$ It seems to be optimal to me. $\endgroup$ Oct 1, 2014 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, 2014 at 21:37
5
$\begingroup$

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

$\endgroup$
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, 2014 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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