LengthOfAString 2002-02-25 22:25:56 2005-03-18 22:16:10 Definition equality of strings empty string \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} 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 \emph{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 \emph{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 \emph{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.