a power of a string

A power of a string means repeating that string a fixed number of times, like stamping the same rubber stamp several times in a row. Writing w^3 just means w w w, the string w concatenated with itself three times. So if w = ab then w^3 = ababab. It is the string version of what exponents do for numbers, but using concatenation instead of multiplication.

Precisely, for a string w and a whole number k, the power w^k is defined by repeated concatenation: w^0 = ε (zero copies gives the empty string, exactly as any number to the power 0 is a kind of neutral starting point), and w^(k+1) = w^k w (one more copy than the previous power). From this, w^1 = w, w^2 = ww, and so on. A neat consequence is that the length multiplies: |w^k| = k times |w|. This builds directly on concatenation, just applied to the same string over and over.

Powers let us name infinite families of strings compactly, which is the engine behind many famous examples. The pattern a^n b^n (n copies of a followed by n copies of b) is the textbook example of a language that no finite automaton can recognize, because counting how many a's appeared requires unbounded memory. Powers of a single symbol, like a^n, also let us state things like the language of even-length strings of a's. Whenever you see an exponent on a string or symbol, read it as that many repeated copies.