length of a string

Suppose we have a string $w$ on alphabet $\mathrm{\Sigma }$. We can then representthe 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$ mustbe a “letter” from the alphabet). Then, the length of $w$ is $n$. Thelength 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$, sincethe 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 asa single symbol.

A “special case” occurs when $\parallel w\parallel =0$, i.e. it does not have any symbolsin 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, thenyou 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$, andfor 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.