Лексикографический порядок

Лексикографический порядок — отношение линейного порядка на множестве слов длины $n$ над некоторым упорядоченным алфавитом $\Sigma$. Своё название лексикографический порядок получил по аналогии с сортировкой по алфавиту в словаре.

Слово a предшествует слову b ($a<b$), если первые $m$ символов слов совпадают, а $m+1$ символ слова a меньше (относительно отношения порядка, заданного в $\Sigma$) $m+1$ символа слова b.

Примеры

• естественный порядок на неотрицательных целых числах в любой позиционной системе счисления, записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999)
• порядок слов в словаре. Предполагается, что буквы можно сравнивать, сравнивая их номера в алфавите. Тогда лексикографический порядок — это, например, А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.