I'm trying to figure out a way to implement this kind of a Turing machine that accept the following language:

$$\Sigma = \{ 0,1,2 \}, \quad\quad L(A) = \{ abc \mid a=b \land c = a^R \}$$

I was thinking of a 3-tape Turing machine or using $\#$ symbol that separates the $a$, $b$ and $c$, but I'm struggling for the $c$ part.

I only need Implementation-level or the way it works.

  • 1
    $\begingroup$ For example a=12332, b=12332 and c= 23321. You have 123321233223321 on tape and accept, is this example correct? Can you use one tape or two tapes? By "way it works" do you mean textual description how to accept it? What are implementation details? Can you use NDTM? $\endgroup$ – Evil Mar 18 '19 at 20:13
  • $\begingroup$ yes, that example is correct $\endgroup$ – Xi N Mar 18 '19 at 20:16
  • $\begingroup$ @Evil, just a description level, and any type of TM. $\endgroup$ – Xi N Mar 18 '19 at 20:40
  • $\begingroup$ Please do not interleave LaTeX and ordinary text. Place the entirety of LaTeX code between $ tags. $\endgroup$ – dkaeae Mar 19 '19 at 8:20

I will use two tapes with deterministic Turing Machine.

Say you have $123321233223321B$ on first tape as input, where B is blank symbol.

At first use three states counter and add some symbol to the second tape, say # every third symbol. Check whether input is divisible by 3 (otherwise reject).

After first iteration you have:

Here you do not reject, as it is divisible by 3.
Now move elements from first tape to second one. After this step you have:

Compare elements from second tape with first one (deleting from first one). After that step you have:

Place head on first tape at the beggining and head of second tape at the end. Compare char by char moving in oposite directions (erasing symbols). If anywhere during comparison there was a mismatch then reject, otherwise accept (if this is required leave something in the first tape at that point).

| cite | improve this answer | |
  • $\begingroup$ Is it possible to find the number of steps a TM will take to recognize a string with size of x. $\endgroup$ – Xi N Mar 18 '19 at 21:04
  • $\begingroup$ Yes, I think ot is quite straightforward. Counting reads x elements, writes x /3 times, then rewrite x/3 elements (it may be optimised), than compare x/3 elements, then seek end, it gives x/3 moves to second tape, compare x/3 elements. This is for accepred string, for rejected it may stop after x steps if not divisible by 3 or at any compare later on. $\endgroup$ – Evil Mar 18 '19 at 22:14

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.