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 < s_2 \implies rank(s_1) < 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.
Algorithm for ranking members of a regular language?
fl.formal languages;automata theory;regular language;regular expressions
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 &\text{if $u \in L$} \\0 &\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| < |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$.