Lexikografisk ordning

Lexikografisk ordning är en relation av linjär ordning på en uppsättning ord över något ordnat alfabet . Den lexikografiska ordningen fick sitt namn i analogi med alfabetisk sortering i en ordbok . $\Sigma$

Definition

Ett ord föregår ett ord ( < ) if $\alfa$ $\beta$ $\alfa$ $\beta$

eller de första tecknen i dessa ord är desamma, och det -te tecknet i ordet är mindre än (med avseende på den givna ordningen) det -e tecknet i ordet (till exempel ABAK < ABRACADABRA, eftersom de två första bokstäverna av dessa ord är desamma, och den tredje bokstaven i det första ordet är mindre än den andra); $m$ $m+1$ $\alfa$ $\Sigma$ $m+1$ $\beta$
eller ordet är början på ett ord (till exempel MATH < MATH; se sammanlänkning ). $\alfa$ $\beta$

Exempel

Ordordning i en ordbok . Det antas att bokstäver kan jämföras genom att jämföra deras siffror i alfabetet . Till exempel går följande ord i lexikografisk ordning: A < AA < AAA < AAB < AAV < AB < B < ... < YAYA.
Naturlig ordning på icke-negativa heltalsvärden i alla positionsnummersystem skrivna i ett bitrutnät med fast längd (000, 001, 002, 003, 004, 005, ..., 998, 999). $n$