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

<p>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}\}$.</p>

<p><strong>EDIT</strong>. 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$.</p>

CC BY-SA 3.0
2014-10-05T11:25:28.620Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-10-04T22:22:13.410Z
2014-10-06T16:36:11.070Z
2014-10-06T16:36:11.070Z
J.-E. Pin
<p>You can show $ |L|^i $ is a tight upper bound by using the following language:</p>

<blockquote>
  <p>$ L = \{ ab,aab,aaab,\ldots,a^kb \mid k \geq 1 \}. $</p>
</blockquote>

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

<blockquote>
  <p>$ U = \{a,aa,aaa,\ldots,a^k \mid k \geq 1 \} $. </p>
</blockquote>

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

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

CC BY-SA 3.0
2014-10-01T20:11:28.147Z
Seeing as we made independently the same guess, I wonder whether the lower bound is optimal.
Emil Jeřábek
CC BY-SA 3.0
2014-10-01T20:54:04.610Z
It seems to be optimal to me.
Ryan Dougherty
CC BY-SA 3.0
2014-10-01T21:37:33.033Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-10-01T18:59:30.850Z
2014-10-01T21:23:53.090Z
2014-10-01T21:23:53.090Z
Abuzer Yakaryilmaz
<p>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?</p>

<p>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] \}$.</p>

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

CC BY-SA 3.0
2014-10-01T18:51:27.613Z
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|\}$).
Emil Jeřábek
CC BY-SA 3.0
2014-10-01T18:59:40.977Z
Thanks on the first one. For the lower bound, is that attained when all the words have the same length?
Ryan Dougherty
CC BY-SA 3.0
2014-10-01T19:01:38.317Z
No. The *upper* bound is attained when all words have the same length.
Emil Jeřábek
CC BY-SA 3.0
2014-10-01T19:50:16.810Z
@EmilJeřábek oh duh, you're right.
Ryan Dougherty
<fl.formal-languages><finite>
Bounds on size of self-concatenation of Finite Languages
Ryan Dougherty
# Bounds on size of self-concatenation of Finite Languages

(Asked by: username_0 on 2014-10-01)

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.

**Tags:** fl.formal-languages, finite
> **Comments:**
> **username_1**: 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|\}$).  
> **username_0**: Thanks on the first one. For the lower bound, is that attained when all the words have the same length?  
> **username_1**: No. The *upper* bound is attained when all words have the same length.  
> **username_0**: @EmilJeřábek oh duh, you're right.  

---

## 2 answers

### Answer by username_3 on 2014-10-01. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_1**: Seeing as we made independently the same guess, I wonder whether the lower bound is optimal.  
> **username_0**: It seems to be optimal to me.  
> **username_1**: 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.  

---

### Answer by username_2 on 2014-10-04. Score: 5

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

> **Comments:**
> **username_1**: 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.  

---

