Foundations · Lesson 2

Factors

Definition

In other words, $u$ appears as a contiguous block inside $w$. Every word is a factor of itself, and the empty word $\epsilon$ is a factor of every word.

A factor uses consecutive positions, unlike a subsequence. In the literature, factors are sometimes called substrings or subwords — but be aware that “subword” is also used for subsequences: sequences formed by deleting zero or more symbols while keeping the remaining symbols in their original relative order. For example, aba is a subsequence of abba (delete the second b), but not a factor of it, since the letters a and b are not consecutive there.

Prefixes and suffixes

Every prefix and every suffix is a factor. The word 001001 has prefixes ε, 0, 00, 001, 0010, 00100, 001001 and suffixes ε, 1, 01, 001, 1001, 01001, 001001.

Proper factors

Note that “proper” means shorter than the whole word; it does not mean “nonempty.” Both $\epsilon$ and the word itself are factors; $\epsilon$ is proper (if $w$ is nonempty), and the whole word is not.

Occurrences

Occurrences may overlap: the word aba occurs at positions 1, 3, 5 in abababa:

Try it: classify a selection

Select a range below and the interface will classify it as a factor, prefix, suffix, or proper factor: