Изменения

Перейти к: навигация, поиск

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

447 байт добавлено, 03:30, 12 ноября 2011
Определение
== Определение ==
Пусть дано линейно упорядоченное множество <tex>~E=\{e_1<e_2<e_3<...<e_k\}</tex> {{---}} алфавит. Словом назовем упорядоченное множество <tex> ~S </tex> элементов алфавита <tex> ~A </tex>. Тогда если на алфавите <tex> A </tex> задан порядок, то порядок задан и на слове <tex> ~S </tex>. Тогда говорят, что множество слов <tex> ~A </tex> задано в лекcикографическом порядке, если для <tex>\forall i \in A </tex> <tex>\forall j \in A </tex> таких, что <tex> i < j </tex> выполнено, что слово <tex> ~A_i </tex> меньше, чем слово <tex> ~A_j </tex>.
 
Это определение можно обобщить до объектов: Если нам даны два объекта <tex> ~P </tex> и <tex> ~Q </tex>, то <tex> ~P </tex> меньше, чем <tex> ~Q </tex>, если объект <tex> ~P </tex> является префиксом <tex> ~Q </tex>, либо если первые <tex> ~i </tex> элементов объектов совпадают, а <tex> ~P_i < ~Q_i </tex>.
== Сравнение слов ==
Анонимный участник

Навигация