# turing machine for the language L ={w#w' where w<w'}

I'm blocked with a question for a long time.

L ={X=w#w' where w < w' and w,w' in {0,1}* }

So i'm trying to find :

1-a deterministric turing maching for the language L.

2-a non deterministic for L.

example :

      w=01 w'=111 --> X in L.

w=1 w'=011 -->  X is **not** in L.


For the deteministic machine , i have an idea only when |w|=|w'|, it's only comparing an alphabet in the first word with an alphabet in the second word.

but i don't know how to solve it when we have two different length ; like my second example .

Do you have any idea for the turing machine?

Thank you.

• What does w < w' mean here? – Raphael Jan 7 '18 at 15:22
• we have a canonical order , 0<1<00<01<000<001<..... , so the question : is w before w'?i think i made an error in my example in the post. – zak zak Jan 7 '18 at 15:32
• So, lexicographic? – Raphael Jan 7 '18 at 17:02
• @Raphael ,yes . – zak zak Jan 7 '18 at 17:21

• If the head of TM reaches the word separator $$\#$$ or the blank symbol (say $$\$$ or something), finish the comparison. If both words end simultaneously (i.e. when $$\left| w \right| = \left| w' \right|$$), then $$w = w'$$. If not, the shorter word is less than the other in the lexicographic order.
First, you can compute $|w|$ and $|w'|$. For the minimum between of them, proceed with your algorithm, comparing bit by bit. If they equal for all the bits, the longer one is the "greater" and then you can decide if the given word belongs to $L$.