# length of a string

Suppose we have a string $w$ on alphabet $\Sigma$. We can then represent the string as $w=x_{1}x_{2}x_{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 $\|w\|$.

For example, if our alphabet is $\Sigma=\{a,b,ca\}$ then the length of the string $w=bcaab$ is $\|w\|=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 $\|w\|=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.

Title length of a string LengthOfAString 2013-03-22 12:29:16 2013-03-22 12:29:16 mathcam (2727) mathcam (2727) 7 mathcam (2727) Definition msc 03C07 equality of strings empty string