patternMinor
A modified version of two way DFA
Viewed 0 times
dfaversionwaymodifiedtwo
Problem
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
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:
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:
- Check parity of input's lenght
- 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.
- Place marker on the first cell of input and on first cell of second half of the input
- 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 $\das
Solution
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".
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".
Context
StackExchange Computer Science Q#60034, answer score: 3
Revisions (0)
No revisions yet.