5
$\begingroup$

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?
$\endgroup$
  • $\begingroup$ 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". $\endgroup$ – Michael Wehar Apr 25 '16 at 18:52
10
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.
$\endgroup$

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.