length of a string


Suppose we have a string w on alphabet Σ. We can then represent the string as w=x1x2x3xn-1xn, where for all xi (1in), xiΣ (this means that each xi 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 Σ={a,b,ca} then the length of the string w=bcaab is w=4, since the string breaks down as follows: x1=b, x2=ca, x3=a, x4=b. So, our xn is x4 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 λ to represent the empty string: w=λ. This is similar to the practice of using β to represent a space, even though a space is really blank.

If your alphabet contains λ 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 x1xn just as before, and similarly v=y1ym. We say v is equal to w if and only if both m=n, and for every i, xi=yi.

For example, suppose w=bba and v=bab, both strings on alphabet Σ={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