Leksikografisk rækkefølge

Leksikografisk rækkefølge er et forhold mellem lineær rækkefølge på et sæt ord over et ordnet alfabet . Den leksikografiske orden har fået sit navn i analogi med alfabetisk sortering i en ordbog . $\Sigma$

Definition

Et ord går forud for et ord ( < ) if $\alfa$ $\beta$ $\alfa$ $\beta$

eller de første tegn i disse ord er de samme, og det -te tegn i ordet er mindre end (med hensyn til den givne rækkefølge) -te tegn i ordet (f.eks. ABAK < ABRACADABRA, da de første to bogstaver af disse ord er de samme, og det tredje bogstav i det første ord er mindre end det andet); $m$ $m+1$ $\alfa$ $\Sigma$ $m+1$ $\beta$
eller ordet er begyndelsen af et ord (for eksempel MATH < MATH; se sammenkædning ). $\alfa$ $\beta$

Eksempler

Ordstilling i en ordbog . Det antages, at bogstaver kan sammenlignes ved at sammenligne deres tal i alfabetet . For eksempel går følgende ord i leksikografisk rækkefølge: A < AA < AAA < AAB < AAV < AB < B < ... < YAYA.
Naturlig rækkefølge på tal med ikke-negative heltalværdier i ethvert positionelt talsystem , skrevet i et bitgitter med fast længde (000, 001, 002, 003, 004, 005, ..., 998, 999). $n$