Foundations: Alphabets, Strings & Languages

the length of a string

The length of a string is just how many symbols it contains, exactly like counting the beads on the wire or the letters in a word. The string cat has length 3 because you write three letters. There is nothing subtle here: you count symbols, including repeats, from the first to the last.

We write the length of a string w as |w| (read aloud as the length of w). For example |ab| = 2, |aaa| = 3, and |b| = 1. By convention the empty string, written ε (epsilon), has length zero: |ε| = 0, because it contains no symbols at all. Length counts positions, so |aa| = 2 even though both positions hold the same symbol a; repetition still adds to the count.

Length is a workhorse measure throughout the theory. It is how we state the size of an input (so we can ask how much time or memory an algorithm uses as |w| grows), it appears in patterns like a^n b^n where the two halves must have equal length, and it is central to the pumping lemma, which talks about strings longer than some fixed length. Whenever you read about the size of a problem instance, length is usually what is meant.

|abba| = 4, |a| = 1, |ε| = 0. Length adds under concatenation: |xy| = |x| + |y|, so |ab| + |ba| gives |abba| = 4.

Length counts symbols including repeats; the empty string has length 0.

The empty string has length 0, not 1. A common slip is to think ε occupies a position; it does not, which is why |ε| = 0.

Also called
|w|length字串長度