<p>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).</p>

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

CC BY-SA 3.0
2016-04-24T01:11:04.250Z
2016-04-24T02:41:10.317Z
2016-04-24T02:41:10.317Z
Jeffrey Shallit
<p>One answer here are multihead automata, see for example the survey</p>

<p>Marek Chrobak: Hierarchies of one-way multihead automata, <a href="http://www.sciencedirect.com/science/article/pii/0304397586900939" rel="nofollow">http://www.sciencedirect.com/science/article/pii/0304397586900939</a> .</p>

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

<ul>
<li>advance two heads $h_2,h_3$, guessing when they have reached the 2/3 spot;</li>
<li>advance all the heads ($h_2$ going backwards), rejecting on any mismatch, until $h_3$ reaches the end;</li>
<li>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).</li>
<li>otherwise accept.</li>
</ul>

CC BY-SA 3.0
2016-04-23T12:21:14.513Z
2016-04-23T12:36:20.520Z
2016-04-23T12:36:20.520Z
Klaus Draeger
<p>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. </p>

<ol>
<li>What is the simplest <em>non-universal</em> 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.</li>
<li>Are there well studied classes of non-universal automata accepting non-context free languages? </li>
</ol>

CC BY-SA 3.0
2016-04-25T18:52:41.900Z
You could use a multi-stack pushdown automaton with bounded phase switching.  If you're looking to learn more about these automata, I particularly like the paper "The Tree Width of Auxiliary Storage".
Michael Wehar
<automata-theory>
Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$
verifying
# Simplest Machine Model Accepting $L = \{ww^Rw\;|\; w\in \Sigma^*\}$

(Asked by: username_0 on 2016-04-23)

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?

**Tags:** automata-theory
> **Comments:**
> **username_1**: You could use a multi-stack pushdown automaton with bounded phase switching.  If you're looking to learn more about these automata, I particularly like the paper "The Tree Width of Auxiliary Storage".  

---

## 2 answers

### Answer by username_2 on 2016-04-24. Score: 12 | Accepted answer

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 by username_3 on 2016-04-23. Score: 3

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.


---

