# Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time

This question is taken from an exam of a Computer Theory Course.

Describe how a NON-Deterministic Turing Machine with two tapes recognize in linear time palindrome strings with even length that have the form: $L=\{ww^R\mid w\in\{a,b\}^+\}$.

• Tape 1: Read-Only & monodirectional
• Tape 2: Read and Write, bidirectional

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

My guess:

With determinism and $L = \{{wcw^R | w \in \{a,b\}^+ \}}$ I copy the input from tape 1 onto tape 2, then I check if the first part of the tape is equals to second part using two markers, $X$ for $a$ and $Y$ for $b$ to keep track of the current iteration.

In every iteration of the algorithm I check if there is a corresponding $a$ (or $b$) in the second part of the tape, reading the tape backwards.

In the last iteration, if i read only $X$ or $Y$ i accept, otherwise reject.

With non-determinism: i need to guess where is the center of the tape. One of the configuration in the computation tree would be $wq_cw^R$ where $q_c$ identify the state representing the string's center. Here i can do the same verification for the deterministic version of the problem.

• Is this exam currently ongoing, or is this a past exam that you are studying from? – Ben I. Nov 1 '17 at 16:08
• It is a question given 1 years ago – Jack Nov 1 '17 at 16:13
• Do you have permission from the professor to post the exam question online for the whole world to see? – mikeazo Nov 1 '17 at 18:04

Hint. Suppose that, instead, the alphabet was $\{a,b,c\}$ you wanted to recognize
$$\{wcw^{\mathrm{R}}\mid w\in\{a,b\}^+\}\,.$$
• Reading your comment, another question comes to mind. What if i have to recognize all palindrome strings over the whole $\Sigma^*$ ? I just made another question here: Limited Turing Machine for Palindromes – Jack Nov 8 '17 at 12:36