Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

Question

Let $\Sigma$ be a finite alphabet. A trivial finite automaton can accept the language $L_1 = \{w\;|\;w\in \Sigma^*\}$. A simple pushdown automaton can accept the language $L_2 = \{ww^R\;|;w\in \Sigma^*\}$ where $w^R$ is the reverse of $w$, i.e., the string obtained from $w$ by reading it backwards.

1. What is the simplest non-universal machine model which accepts the language $L_3 = \{ww^Rw\;|\;w\in \Sigma^*\}$? Note that $L_3$ can be easily accepted by a queue automaton, but queue automata are universal.
2. Are there well studied classes of non-universal automata accepting non-context free languages?

Answer 1

You don't need nondeterminism or multiple heads. Even a 2DPDA can accept this language: push 2 counters per symbol while scanning from left endmarker to right; then pop 3 per symbol while scanning left until stack empty. At this point you're at the boundary between first w and w^R. Scan left, pushing onto stack until left endmarker. Now stack has w^R. Play the same game again with the counters, then move right comparing stack contents to symbols read. If success, then first 2/3 of string is w w^R. A similar trick can be used to ensure last 2/3 of string is w^R w. And of course, precede all of this with a single scan to make sure input is of length == 0 (mod 3).

There is an intro to 2DPDA's in my book, A Second Course in Formal Languages and Automata Theory.

Answer 2

One answer here are multihead automata, see for example the survey

Marek Chrobak: Hierarchies of one-way multihead automata, http://www.sciencedirect.com/science/article/pii/0304397586900939 .

Specifically, a nondeterministic 2-way automaton with three heads could decide this language, a sketch of its operation being:

• advance two heads $h_2,h_3$, guessing when they have reached the 2/3 spot;
• advance all the heads ($h_2$ going backwards), rejecting on any mismatch, until $h_3$ reaches the end;
• advance $h_1,h_2$ until they reach the end, rejecting if one finishes early (which means that they didn't meet or moved past each other, i.e. the guessed position was wrong).
• otherwise accept.