# length of a string

Suppose we have a string $w$ on alphabet $\mathrm{\Sigma}$. We can then represent
the string as $w={x}_{1}{x}_{2}{x}_{3}\mathrm{\cdots}{x}_{n-1}{x}_{n}$, where for all ${x}_{i}$
($1\le i\le n$), ${x}_{i}\in \mathrm{\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 $\parallel w\parallel $.

For example, if our alphabet is $\mathrm{\Sigma}=\{a,b,ca\}$ then the length of the string $w=bcaab$ is $\parallel w\parallel =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 $\parallel w\parallel =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}\mathrm{\cdots}{x}_{n}$ just as before, and similarly $v={y}_{1}\mathrm{\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 $\mathrm{\Sigma}=\{a,b\}$. These strings are not equal because the second symbols do not match.

Title | length of a string |
---|---|

Canonical name | LengthOfAString |

Date of creation | 2013-03-22 12:29:16 |

Last modified on | 2013-03-22 12:29:16 |

Owner | mathcam (2727) |

Last modified by | mathcam (2727) |

Numerical id | 7 |

Author | mathcam (2727) |

Entry type | Definition |

Classification | msc 03C07 |

Defines | equality of strings |

Defines | empty string |