0
$\begingroup$

I need to design a turing machine that accepts $L=\{ww^Rw\mid w\in\{0,1\}^*\}$.

$w^R$ is the reverse of $w$.

I don't have a good idea yet how to do that, I know I should check:

  1. the length of the word must be equal $0\mod 3$

  2. $ww^R$ is a palindrome

  3. the prefix $w$ equal to the suffix $w$.

I thought maybe to divide the word to three parts and use non deterministic TM to move from one part to another. Need help with the algorithm.

$\endgroup$
  • $\begingroup$ This is, ultimately, a programming question. Pick any programming language you are comfortable with (RAM programs, C, $\lambda$-calculus, ...), write the program, then translate/compile it into TM. $\endgroup$ – Raphael Apr 29 '17 at 8:32
  • $\begingroup$ Please check if you really need to do this. Giving a formal definition of a TM for this language is not very hard, but very tedious, and has (imho) little teaching value. I think it's more likely that you are supposed to give a high-level description of how the machine is supposed to work. $\endgroup$ – Raphael Apr 29 '17 at 8:33
  • $\begingroup$ Correction: I was thinking of a DTM. An NTM is considerably more compact. $\endgroup$ – Raphael Apr 29 '17 at 9:03
1
$\begingroup$

Here is an idea for an non-deterministic Turing machine: guess the borders between $w$ resp. $w^R$ non-deterministically and verify that the parts do indeed match.

With a little more detail:

  • Mark the first input symbol. Put additional marks on two more arbitrary symbols (choose non-deterministically).
  • Consume the word (i.e. overwrite it with blanks) in lock-step starting from each mark; move right from the first and third, and left from the second.
    • If the three marks are on different symbols at any step, reject.
    • If they are the same, overwrite with blank and move all marks in their direction by one symbol.
  • If all three marks reach blank simultaneously, accept.
  • Otherwise, reject.

I'll leave the details and proof of correctness as exercise.

$\endgroup$
  • $\begingroup$ What do you mean "guess the Borders between w resp." ? @raphael $\endgroup$ – Nick Nov 8 '17 at 1:25
  • $\begingroup$ @Nick That would be bullet 1. $\endgroup$ – Raphael Nov 8 '17 at 6:40
2
$\begingroup$

I suggest a deterministic solution using some basic TM trickery.

First you need to identify the parts. Suppose we tag the 0,1 symbols by replacing them by symbols, e.g. A,B (A~0, B~1) - so that we know what we already "tagged" but keep the data "intact". The TM works in a simple loop: move far left, tag the first untagged element, move to far right, tag first two untagged elements. If at some point the tags from left and the tags from right meet, we have found the end of W prefix. If the tags don't meet well, then the length of the input is not divisible by 3 and the TS says NO. Suppose we used A,B tags on left and C,D tags on right (so we can always find the end of W prefix). We split in the C,D part into WR and W in a similar way.

Suppose that the first part now consist of A,B symbols, the middle of C,D symbols and the last of E,F symbols. The TS now reads the three sections in parallel (while the middle one is read in reverse) and compares them in a simple loop, while rewriting the correct parts with some special # symbol. First, move to the left to find the first non-# symbol (which is either A or B). Remember it (use two sets of states, one corresponding to A and one corresponding to B) and replace the symbol by #. Move right until you reach the end of C,D section (the first symbol E,F or # signifies the end), and check if the previous symbol corresponds to the remembered value (A~C, B~D). If it does not, answer NO. Otherwise replace it by # and move to the first E/F-symbol and again check (A~E,B~F) and replace with #. Repeat until there are no non-# symbols left. Once that happens, the answer is YES.

$\endgroup$

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.