What would be the explicit formula of a " dictionary" function / relation that would put in the "dictionary order" all the words of a natural language ( having an alphabet)?

I think that one of the main difficulties here is that a lexicographic order relation only "works" with n-tuples having the same size. So, apparently, we need as many ordering relations as possible sizes for a word.

My reflexion does not go further than this:

(1) We need W the set of all words

(2) We need a function "Letter" having as domain W and associating each word with an n-tuple such that if the nth letter of a word is the mth letter of the alphabet, then the nth element of the n-tuple is m

     For example: Letter ( cat) = (3,1,20) 

(3) Then an equivalence relation classifying n-tuples according to their length

(4) Then a relation that, in each equivalence class, would put in order lexicographically the word-representing n-tuples.

In the equivalence class of (3,1,20) this relation would be :

(a,b,c ) < ( d,e,f) iff

(1) a

(2) or, if a=d, b

(3) or, if b=e , c < f .

(6) Finally we would need the inverse of the function L to recover words from n-tuples.

This suggestion is clearly is far from being satisfying.

Remark.- I add the tag " computer science" for maybe the problem can be solved using a kind of "algorithm".

  • 1
    $\begingroup$ The lexicographic order can be defined on arbitrary partial orders; you don't need to map into the integers. $\endgroup$ – Patrick Stevens May 5 at 8:22

This is one way of defining lexical order on words. First you define an alphabet $\Sigma$ the set of all the letters you are dealing with. Then $\Sigma^*$ is the Kleene closure of that set. That is the set of all tuples (also called strings or words) made with elements from $\Sigma$ including "" which is the empty string.

If you have an ordering on on the letters in your alphabet $\geq_\Sigma : \Sigma^2$ then you can define a dictionary ordering this way $$ \geq_{\Sigma^*} := \{ \langle x,y \rangle \in \langle \Sigma^*,\Sigma^* \rangle | y = "" \vee (h(x) \geq_\Sigma h(y) \wedge h(x) \neq h(y)) \vee (h(x) = h(y) \wedge t(x) \geq_{\Sigma^*} t(y) \} $$

Where h(x) is the head function that gives the first character of the tuple and t(x) is the tail function that gives the rest of the tuple not including the head.

  • 1
    $\begingroup$ @QthePlatypus.I'll have to make some progress to understand this. Thanks for answering my question! $\endgroup$ – Eleonore Saint James May 5 at 9:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.