Following an exercise from Hopcroft-Ullman's Introduction to automata theory:

Let's define $k-MDFA$ as two way deterministic finite automaton with $k$ markers, similarly to two way $DFA$ but with ability to place (or pick up) a marker on the input cell currently under the head, but with limitation to placing at most $k$ markers at any time during computation, and with single cell only being able to hold at most 1 marker at any given time.

Formally, it's a tuple $A=(Q, \Sigma, \delta, s, F)$ where

  • $Q$ is finite set of states
  • $\Sigma$ is the input alphabet
  • $\delta : Q \times (\Sigma \hspace{2pt}\cup \hspace{2pt} \{\vdash, \dashv\})\times \{0,1\} \rightarrow Q \times \{\textbf{L,R}\}\times \{0,1\}$ is the transition function
  • $s$ is the initial state and $F$ is the set of accepting states

Input tape of the automaton for word $w \in \Sigma^*$ is $\vdash w \dashv$.

Moreover the transition function satisfies $\delta(q,\vdash,m) = (q', R, m')$, $\hspace{2pt}\delta(q, \dashv, m) = (q', L, m')$ for all $q \in Q, \hspace{2pt} m \in \{0,1\}$ and for some $q' \in Q $ and $m' \in \{0,1\}$ (we do not allow automaton to leave the input).

If automaton attempts to place more than $k$ markers on the tape, the computation stops with rejection.

I have proved that $1-MDFA$ recognize exactly regular sets, but I can also show that with $2-MDFA$ I can recognize language $\{ ww : w \in \Sigma^*\}$, which is not a context free language. The second fact is fairly simple - here's an outline of how such automaton would work:

  1. Check parity of input's lenght
  2. Locate the middle of input by placing markers at both ends of the word, and then moving them one step closer towards the middle alternatingly.
  3. Place marker on the first cell of input and on first cell of second half of the input
  4. Compare letters under markers, if they differ enter reject state, if they are same, move both markers 1 step to the left and repeat. If you are about to move right marker onto symbol $\dashv$ enter accept state.

As such, clearly languages recognized by $k-MDFA$ are not contained in $CFL$ for $k \geq 2$.

My questions are:

  1. Does increasing the amount of markers increase the computation power of $k-MDFA$ for $k \geq 2$?
  2. Does allowing nondeterminism increase computation power of $k-MDFA$?
  3. Can $k-MDFA$ recognize all context-free languages? If so, what's the minimal $k$ capable of expressing $CFL$?

Any references are welcome, if the question shows ignorance in the subject, I apologise.

  • 2
    $\begingroup$ You ask three very different questions in one post; please don't do that. Ask one first, and then the others in their own posts; you may link back here for the setup details. $\endgroup$ – Raphael Jun 26 '16 at 21:34
  • $\begingroup$ $MDFA$ to my best knowledge has multiple initial states. And $k$ is branching factor - is it consistent with your definition? Also $\{ww : w \in \Sigma^*\}$ is co-context free. 1) for $k > 2$ you can always convert automaton to different $k$ and from any $k-MDFA$ you can create NFA with n states having branching k can be simulated by a k-MDFA with k · n states - according to Kappes $\endgroup$ – Evil Jun 26 '16 at 22:35

To answer your first question, see: Burkhard Monien, Two-way multihead automata over a one-letter alphabet. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1980) https://eudml.org/doc/92118

".. we show that for languages over a one-letter alphabet two-way automata with $k+1$ heads are more powerful than two way automata with $k$ heads."

This improves over a similar result of the same author and others for two-letter alphabets, one-way automata, or stepping from $k$ to $k+4$-heads, see the paper.

Also an interesting quote "It is wellknown that SPACE(log n), the class of languages acceptable within space bound log n, is identical with the class of languages acceptable by two-way multihead automata".


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.