Non-Deterministic Turing Machine Algorithm

Question

I'm having trouble with this question:

Write a simple program/algorithm for a nondeterministic Turing machine that accepts the language:

$$ L = \left\{\left. xw w^R y \right| x,y,w \in \{a,b\}^+, |x| \geq |y|\right\} $$

Answer 1

Outline: First nondeterministically choose where the cut-off between $w$ and $w^{\text{R}}$ is. Then compare and cross-out symbols to the left and right of this cut off until you find the first $i$ such that the symbol $i$ cells to the left of the cut-off is different than the symbol $i$ cells to the right of the cut off. Now check that there are at least as many non-crossed symbols to the left as there are to the right.

Answer 2

Look at the language... it is really the language $(a \mid b \mid c)^+ (a a \mid bb \mid cc) (a \mid b \mid c)^+$. A simple DFA will do ;-)

[Never underestimate the sneakiness of questions... but it might just be Hanlon's razor at work.]

Update: Oops, forgot the restriction that $\lvert x \rvert \ge \lvert y \rvert$, but the observation that $w w^R = aa \mid bb \mid cc$ is enough still stands.

Answer 3

EDIT: Well, now that I see what vonbrand meant, this is a bit silly. You can kind of also see from the description of my automaton that there's no real need to bother keeping on checking whether the symbols match once you reach $q_1'$. By moving to $q_2$ immediately rather than bothering with $q_1'$, you accept the same language less complicatedly.

---

This isn't an answer to the question, since what you're asking for is a Turing machine, but I thought it might be worth pointing out that this language is actually context-free (that is, it belongs to a much more restricted class of languages than those defined by Turing machines). Here is the sketch of a pushdown automaton accepting it:

Write the word onto the stack until you non-deterministically guess you have reached the end of $w$, in which case move to a new state $q_1$. In $q_1$, if the next symbol matches the symbol on the top of the stack, pop the stack and move to $q_1'$, otherwise fail (this is to ensure that $w$ has positive length). In $q_1'$, continue to read, popping a symbol off the stack if it matches the symbol just read, and moving to a new state $q_2$ if not. In $q_2$, pop a symbol off the stack for each symbol read, and fail if you ever read a symbol while the stack is empty. Make $q_2$ the only accept state.

This sounds a bit more complicated than it is (perhaps because I'm tired and haven't described it very well). It's just a PDA version of the Turing machine described by Arthur Fischer.

---

Also, here's a grammar for the language:

$S\to AB$

$A\to aA \mid bA \mid cA \mid \epsilon$

$B\to xBy \mid xx \hspace{0.7cm} (x,y\in \{a,b,c\})$

Answer 4

As TaraB hints at, the language is really context free: $$ \begin{align*} S &\rightarrow A S A \\ A &\rightarrow a \mid b \mid c \\ B &\rightarrow A B A \mid A B \mid a a \mid b b \mid c c \end{align*} $$ Here the $S$ production serves to ensure $x$ and $y$ have length at least 1, $A$ serves to give a single symbol for compactness, the $B$ productions add something at the beginning and end, and allow $x$ longer than $y$, and finally place a $aa$, $bb$, or $cc$ (off-)center.