Algorithm for ranking members of a regular language?
Let $A = \{1, ..., k\}$ be an ordered alphabet. Then each word on $A^*$ can be viewed as a number in base $k + 1$ (note that $0$ is never used on purpose). Now define
$$
rank(u) = \begin{cases}
u &amp;\text{if $u \in L$} \\
0 &amp;\text{otherwise}
\end{cases}
$$
Then $rank$ preserves the shortlex (or radix) order, which is the order $\leqslant$ on $A^*$ defined by $u \leqslant v$ if and only if $|u| &lt; |v|$ or $|u| = |v|$ and $u \leqslant_{lex} v$. That is, words are first ordered by length and words of equal length are ordered according to the lexicographic order. Now, if $L$ is regular, $rank$ is easy to compute and is of course one-to-one on $L$.