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.
