HW 4 Q2

Summary:

what is a lexicographic order?

HW 4 Q2

OfirCarmel 20 Dec 2014 11:06

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₁|<|w₂| then w₁ is earlier in the lexicographic order, if they are equal- compare by each simbol as usual.
2- if |w₂|-|w₁|=k>0, define: w'₁= w₁ as w₁(_)^k, where _<x, for any x in (Sigma), and then |w'₁|=|w₂|, and we can compare w'₁ with w₂ 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.

Re: HW 4 Q2

oritmosk 20 Dec 2014 11:33

We use the first definition.
If we were using the second definition, then indeed for any $n$, $0^n$ will always be earlier in the lexicographic order than 1. In this case we will not be able to enumerate all $\Sigma^*$.

Re: HW 4 Q2

OfirCarmel 20 Dec 2014 12:32

well, for me at least, it wasn't that trivial that this is the definition we use.
thus-trying to solve question 2 without it was quite time consuming, apperantly time that I had lost for nothing.
were we suppose to be familiar with this definition somehow? intend to ask:
is there someway I can act next time in order to prevent it from happening?

Re: HW 4 Q2

oritmosk 20 Dec 2014 13:50

First of all, let's think about the construction of an enumerator for $L \in RE$ (Lec 7, slide 21).
We could think of the exact implementation of the enumerator - how would it write $s_1, s_2, ... s_i$, and reach every string in $\Sigma^*$?
If we used the second definition you wrote, then E will always write strings of the form $0^n$. Meaning - it won't be an enumerator for L (there are strings that will never be printed).
Therefore, in order to implement a TM that goes over all strings in $\Sigma^*$, you have to consider the length of the words before the comparison of the letters.
So this could have been a hint that the first definition is the one we should use.

Second of all, in future assignment, we'll try to define specifically anything that wasn't defined in class,
but if you feel there are some definitions that are missing, feel free to ask.

Re: HW 4 Q2

gal_rotem 20 Dec 2014 17:26

Actually, the lexicographic order was defined in lecture 7, slide number 56. We had to somehow count the words in sigma star in order to prove that sigma star is countable, so trivially this gives you a lexicographic ordering.

Last edited on 20 Dec 2014 17:27 by gal_rotem Show more

Re: HW 4 Q2

OfirCarmel 20 Dec 2014 18:20

missed that, thanks!