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

Лексикографічний порядок — відношення лінійного порядку на множині кортежів ${\displaystyle \Sigma ^{*}}$; ${\displaystyle \Sigma }$ — упорядкований алфавіт. Свою назву лексикографічний порядок отримав по аналогії з сортуванням по алфавіту в словнику.

Нехай у списку букв алфавіту ${\displaystyle \Sigma }$ порядок букв фіксований, тобто завжди один і той самий. Тоді цей список визначає повне впорядкування букв, які назвемо відношення передування і позначимо ${\displaystyle <=}$ (${\displaystyle a_{i}<=a_{j}}$, якщо ${\displaystyle a_{i}}$ передує ${\displaystyle a_{j}}$ у списку букв). На основі відношення передування букв — будуємо відношення передування слів, визначене наступним чином: Нехай дано слова ${\displaystyle a_{1}=a_{11}...a_{1m}}$ та ${\displaystyle a_{2}=a_{21}...a_{2m}}$, тоді ${\displaystyle a_{1}<=a_{2}}$, якщо виконується перший або другий пункт.

1. ${\displaystyle a_{1}=\beta a_{i}g,a_{2}=\beta a_{j}d}$ та ${\displaystyle a_{i}<=a_{j}}$ (β, g, d — деякі слова, можливо, порожні, ${\displaystyle a_{i}}$ та ${\displaystyle a_{j}}$ — букви)
2. ${\displaystyle a_{2}=a_{1}\beta }$, де β - непорожнє слово.

Це відношення задає повне впорядкування множин всіх кінцевих слів у алфавіті "${\displaystyle \Sigma }$", яке називається лексикографічним упорядкуванням слів.