Изменения

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

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

4 байта добавлено, 05:26, 27 декабря 2010
Определение
== Определение ==
Пусть дано линейно упорядоченное множество <tex>~A=\{a_1<a_2<a_3<...<a_k\}</tex> - алфавит, <tex>A^*</tex> назовем множество подпоследовательностей конечной длины из алфавита <tex> A </tex>, <tex>A^*=\bigcup^{\infty}_{i=0} A^i</tex>, тогда лексикографическим порядком на множестве <tex>~A^*</tex> назовем такой порядок, при котором, элементы <tex>~x<y</tex> <tex>(x,y \in A^*; x=\{x_1,x_2,...,x_{i_1}\}; y=\{y_1,y_2,...,y_{i_2}\}; x_j,y_j \in A</tex>), то если они удовлетворяют условиям:<br>
* либо <tex>~i_2>i_1</tex> и <tex>\forall j\le{i_1}:x_j=y_j</tex>
* либо <tex>\exists n\le{\min(i_1,i_2)}:\forall j<n:x_j=y_j; x_n<y_n</tex>
Анонимный участник

Навигация