Algorithm for ranking members of a regular language? A little while back, I was reading a paper that mentioned a method for computing an integer 'rank' for a particular string $s \in L$ where $L$ is some regular language. This rank uniquely determines any string in the language and has the property that, for some lexicographic ordering, $s_1 &lt; s_2 \implies rank(s_1) &lt; rank(s_2)$. Another property is that given $rank(s_0)$ we can efficiently determine $s_0$ using an 'unrank' algorithm.

However, the paper wasn't very specific and I don't know where to find a more detailed description of the algorithm. Can anyone point me in the right direction? 

I remember that it involves compiling a regular expression to a DFA and giving the description of the DFA to the ranking algorithm.

Thanks for your help.
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$.