0
$\begingroup$

I'm having some issues constructing a transition diagram of a deterministic Turing machine for $L = \{0^i1^j2^j3^k \ | \ i = j + k\}$

The point where I get stuck is how I should make sure that $i = j + k$

My thoughts:

My thought was to initially do something similar to do something including an addition turing machine where I check that the final tape is of the structure generated by the language i.e we should have 2 $0$s, 1 $1$, 1 $2$ and 3 $1$s = 6 and if it is correct then we'd go through checking if $0$s come before $1$s, $2$s before $1$s and $3$s before $2$s.

I think this is a really complicated way to do it, and that's why I'm asking.

Question: Construct a transition diagram of a deterministic Turing machine for $L = \{0^i1^j2^j3^k \ | \ i = j + k\}$. What I'm asking is for some guidance.

Thanks in advance!

$\endgroup$
0

1 Answer 1

1
$\begingroup$

This is meant to give you a hint, but if you are lost, you could think about doing it in three large steps:

  1. Make a single pass through, making sure that you encounter $0$s followed by $1$s followed by $2$s followed by $3$s. You should think through the end conditions if this process goes smoothly, or what items you might encounter on the tape that could send you to a reject state.

  2. Now check that there are the same number of $1$s and $2$s: go back and find the start of the $1$s. For every $1$, replace it with an $i$, run off to the right and find a corresponding $2$ (which you must also replace with some symbol, such as $T$). Again, think through the end conditions, and how you will know if something unexpected has happened.

  3. Finally, check if $i=j+k$. Run to the beginning of the $0$s, and for every $0$ you replacing (with, say, $o$), run off and find the next $T$ or $3$ and replace that with some other symbol ($F$?). At the end, a pass left will be sufficient to tell you that there are no more $0$s, and a pass right will be sufficient to tell you that there are no remaining $T$s or $3$s.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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