Suppose we have a string $w$ on alphabet $\Sigma$ . We can then represent the string as $w = x_1x_2x_3\cdots x_{n-1}x_n$ , where for all $x_i$ ($1 \leq i \leq n$ ), $x_i \in \Sigma$ (this means that each $x_i$ must be a ``letter'' from the alphabet). Then, the length of $w$ is $n$ . The length of a string $w$ is represented as $ \Vert w \Vert $ .

For example, if our alphabet is $\Sigma = \{ a, b, ca \} $ then the length of the string $w = bcaab $ is $ \Vert w \Vert = 4$ , since the string breaks down as follows: $ x_1 = b$ , $x_2 = ca $ , $x_3 = a$ , $x_4 = b$ . So, our $x_n$ is $x_4$ and therefore $ n = 4$ . Although you may think that $ca$ is two separate symbols, our chosen alphabet in fact classifies it as a single symbol.

A ``special case'' occurs when $\Vert w \Vert = 0$ , i.e. it does not have any symbols in it. This string is called the empty string. Instead of saying $ w = \ $ , we use $\lambda$ to represent the empty string: $w = \lambda$ . This is similar to the practice of using $\beta$ to represent a space, even though a space is really blank.

If your alphabet contains $\lambda$ as a symbol, then you must use something else to denote the empty string.

Suppose you also have a string $v$ on the same alphabet as $w$ . We turn $w$ into $x_1 \cdots x_n $ just as before, and similarly $v = y_1 \cdots y_m $ . We say $v$ is equal to $w$ if and only if both $m = n$ , and for every $i$ , $x_i = y_i$ .

For example, suppose $ w = bba $ and $v = bab$ , both strings on alphabet $\Sigma = \{ a,b \}$ . These strings are not equal because the second symbols do not match.