How to recursively define $w^i$ for $i≥0$

123 Views Asked by At

Given a string $w$, we denote with $w^i$ the string obtained by concatenating $i$ times $w$.

How can I recursively define $w^i$ for $i≥0$?

First of all, what does "concatenate" mean in this context?

2

There are 2 best solutions below

0
On

Concatenate just means write one after the other, so if you have two strings $a$ and $b$ the concatenation is $ab$. In your problem $w^i$ is a string of $i\ w's$, so for $i=4$ you have $w^4=wwww$

4
On

The concatenation of the words $u$ and $v$ is the word $uv$, e.g. if we have the alphabet $\Sigma = \{ a, b, c, d \}$ and the two words $u, v \in \Sigma^*$ (the set of all finite length words over $\Sigma$) with $u = abc$ and $v = dab$ then $$ u \cdot v = abc \cdot dab = abcdab $$ where $\cdot$ is the concatenation operator. If the context allows it, one does not write it, not unlike the multiplication operator.

Your recursive definition is something like \begin{align} w^0 &= \epsilon \\ w^{k+1} &= w^k \cdot w = w^k \, w \end{align} where $\epsilon$ is the empty word, which is the word consisting of no symbols, having length $0$. It has the property $$ w\epsilon = \epsilon w = w \quad (w \in \Sigma^*) $$

See Formal language to get an introduction.