Википедия

Лексикографический порядок: различия между версиями

Интерактивная навигация по истории
[отпатрулированная версия][отпатрулированная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Лексикографический порядок определён не только для слов одной длины.
Строка 1:
'''Лексикографический порядок''' — [[отношение линейного порядка]] на множестве слов[[Слово длины(формальный <math>n</math>язык)|слов]] над некоторым упорядоченным [[Алфавит (формальный язык)|алфавитом]] <math>\Sigma</math>. Своё название лексикографический порядок получил по аналогии с сортировкой по [[алфавит]]у в [[словарь|словаре]].
 
== Определение ==
Слово ''a'' предшествует слову ''b'' (<math>a<b</math>), если первые <math>m</math> символов слов совпадают, а <math>m+1</math> символ слова ''a'' меньше (относительно отношения порядка, заданного в <math>\Sigma</math>) <math>m+1</math> символа слова ''b''.▼
Слово ''a'' предшествует слову ''b'' (<math>a<b</math>), если
▲Слово* ''a'' предшествует слову ''b'' (<math>a<b</math>), еслилибо первые <math>m</math> символов этих слов совпадают, а <math>m+1</math>-ый символ слова ''a'' меньше (относительно отношения порядка, заданного в <math>\Sigma</math>) <math>m+1</math>-ого символа слова ''b''. (например, АБАК < АБРАКАДАБРА, так как первые две буквы у этих слов совпадают, а третья буква у первого слова меньше, чем у второго);
* либо слово ''а'' является началом слова ''b'' (например, МАТЕМАТИК < МАТЕМАТИКА).
 
== Примеры ==
* Порядок [[слово|слов]] в [[словарь|словаре]]. Предполагается, что [[буква|буквы]] можно сравнивать, сравнивая их номера в [[алфавит]]е,. и что отсутствие следующего символа «меньше»Например, чемследующие наличиеслова тамидут любогов символа;лексикографическом тогда лексикографический порядок — это, например,порядке: А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.▼
* Естественный порядок на неотрицательных [[целое число|целых числах]] <math>n</math>-значных числах в любой [[позиционная система счисления|позиционной системе счисления]], записанных в разрядной сетке фиксированной длины (000, 001, 002, 003, 004, 005, …, 998, 999).
▲* Порядок [[слово|слов]] в [[словарь|словаре]]. Предполагается, что [[буква|буквы]] можно сравнивать, сравнивая их номера в [[алфавит]]е, и что отсутствие следующего символа «меньше», чем наличие там любого символа; тогда лексикографический порядок — это, например, А < АА < ААА < ААБ < ААВ < АБ < Б < … < ЯЯЯ.
 
{{algebra-stub}}
Источник — https://ru.wikipedia.org/wiki/Лексикографический_порядок