1
$\begingroup$

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.

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

Hint. Suppose that, instead, the alphabet was $\{a,b,c\}$ you wanted to recognize

$$\{wcw^{\mathrm{R}}\mid w\in\{a,b\}^+\}\,.$$

How would you do that on a deterministic version of the machine you're trying to use? Now, in the real problem, nobody's telling you where the middle of the string is. How would you use nondeterminism to get around that problem?

$\endgroup$
  • $\begingroup$ i made some edits in the question's body after your hint. Thanks! $\endgroup$ – Jack Nov 1 '17 at 22:16
  • $\begingroup$ Well, that's fine but we're not here to grade your attempts. $\endgroup$ – David Richerby Nov 1 '17 at 22:32
  • 1
    $\begingroup$ What could happen if the string is odd? $\endgroup$ – Jack Nov 8 '17 at 0:57
  • $\begingroup$ @Jack Then no computation path will match the two "halves" of the string, since they have different lengths. $\endgroup$ – David Richerby Nov 8 '17 at 8:59
  • $\begingroup$ 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 $\endgroup$ – Jack Nov 8 '17 at 12:36

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.