String Permutation

Question

If we have the string ab, would abab be a permutation of ab? It seems that a permutation is a rearrangement of things but only within the things in our set. In this example, that set is ab.

Answer 1

There are only two permutations of $ab$: $ab$ and $ba$. A permutation is a rearrangement of characters in the string.

A related (but different) concept is that of regular languages. For example, the language

$$(a + b)^*$$

Describes all character sequences of length zero or more whose characters are from the set $\{a, b\}$. Using a canonical enumeration scheme, this language includes $\epsilon$ (the empty string), $a$, $b$, $aa$, $ab$, $ba$, $bb$, ...

The language $$(ab)^*$$ Describes the set of all character sequences formed by repeating $ab$ any number of times. This language includes $\epsilon$, $ab$, $abab$, ...