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