in some of the sources provided in this course (lecture 7, slide 21- for example)- we have been provided with a solution using an assumed list of all the strings over (Sigma)* sorted by lexicorgaphic order, but i didn't see any clear definition of what a lexicographic order is.

if indeed we have defined it, **and** it's different from what's defined in wikipedia (not allowed to post links), **and** I just missed it - please just tell me where i can find it, and accept my apology for asking that.

otherwise-i have some problem understanding some stuff about it:

how do we define a lexicographic order between to words that are'nt of the same size? (any definition i saw used a cartesian multiplication that by definition concerns only words of an equal size)

two possible solutions i can think of are:

1- if |w_{1}|<|w_{2}| then w_{1} is earlier in the lexicographic order, if they are equal- compare by each simbol as usual.

2- if |w_{2}|-|w_{1}|=k>0, define: w'_{1}= w_{1} as w_{1}(_)^{k}, where _<x, for any x in (Sigma), and then |w'_{1}|=|w_{2}|, and we can compare w'_{1} with w_{2} as usual.

method 2 is the string comparison we usually use when not told otherwise.

but if we use method 2 for comparison, then a lexicographic full list of (Sigma)* doesn't necesserally exists for any |Sigma|>1. in the same way that we can't enlist all the rational numbers in a rising order (assuming otherwise would suggest that for any rational number, there is finite number of other, smaller ones. in contradition to the density property)

so in conclusion, i'm confused /: . please correct me if i'm wrong, and clarify your definition of a lexicographic order. if not.