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.

  • $\begingroup$ What does w < w' mean here? $\endgroup$ – Raphael Jan 7 '18 at 15:22
  • $\begingroup$ 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. $\endgroup$ – xmen-5 Jan 7 '18 at 15:32
  • $\begingroup$ So, lexicographic? $\endgroup$ – Raphael Jan 7 '18 at 17:02
  • $\begingroup$ @Raphael ,yes . $\endgroup$ – xmen-5 Jan 7 '18 at 17:21

Here is a sketch of a construction method of the TM:

  • Compare bit by bit from the first bit to the last bit as normal. If equals, proceed to the next bit. Otherwise, it can decide the order.
  • 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.

This idea is the same for both a deterministic TM and a non-deterministic TM. Only a non-deterministic TM can compare bits in a non-deterministic way.

| cite | improve this answer | |

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$.

| cite | improve this answer | |

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.