Strings

An alphabet is a finite, nonempty set Σ of symbols.

For example:

Σ = {a, b}

or

Σ = {0, 1}

or

Σ = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}

A string is a sequence of symbols from Σ.

It is common to use variables to name strings. For example:
u = baa
w = abba

It should be noted that the following statements are true about these strings.

baa ∉ Σ
baa ϵ Σ*

Recall that Σ* is the alphabet which contains lambda (λ). λ is the empty string. It represents a string with the length of 0.

The reason that baa ∉ Σ but baa ϵ Σ* is because Σ* represents every possible combination of the elements {a, b} of Σ.

For Σ = {a, b}, Σ* is countably infinite.

We can show the ordered lexicography of Σ* by writing the elements of Σ* our as {λ, a, b, aa, ab, ba, bb, aaa, aab, aba, ...}.

Concatination
uw = baaabba
uu = baabaa

For any integer n >= 0, uⁿ is the string u, concatenated n times. For example:
 uⁿ = uuu...u
 u³ = baabaabaa