2
$\begingroup$

We know that A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA)is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a Deterministic finite automaton in computational power, and therefore can only parse a regular language.

This language $L = \{ (u\#,v\#)| u, v \in(a,b)^*, |u|=|2v| \}$ is checked by 2-way DFA but not possible to check $|u|=|2v|$ by DFA ,so my question is how could we say 2-way DFA is equivalent to DFA? Because by 2-way DFA we are able to check $|u|=|2v|$ but not possible by DFA or 1-way DFA.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

The language $L=\{ (u\#,v\#) \mid |u|=|2v|\}$ from your question is actually a two-dimensional language, that is a relation between two strings, each written on their own input tape. In that way the condition $|u|=|2v|$ is easy to check, even with a deterministic one-way (two-tape) automaton: when the head moves one cell on the $v$-tape, the head on the $u$-tape moves two cells.

On the other hand, the condition $|u|=|2v|$ is indeed impossible to check for a classical, single tape, finite state automaton.

In general, for a single tape, the two-way finite automaton is as powerful as the classical (one-way) finite state automaton. (Both deterministic and non-deterministic variants.) One of the possible proof I have seen uses the concept of "crossing sequences", for each cell we record the sequence of states that the 2NFA had when entering/leaving that cell from/to its left neighbour. This in a way summarizes the 2-way computation in a one-way fashion.

Perhaps the number of tapes is not what determines the difference in power. A two-tape automaton has two heads, which can independently read letters. If a one-tape automaton is equipped with two heads, we can also accept languages like $\{ u\#v \mid |u|=|2v|\}$.

Improve this answer
$\endgroup$
9
  • $\begingroup$ One thing don't understand for $|u|=|2v|$, $|v|=1$, we need to check two cells of $u$ tape because $|u|=2$, but you did converse, that don't understand? $\endgroup$
    – user19121278
    Jun 8 at 18:54
  • $\begingroup$ Two tape with one way DFA is more powerful than DFA , I mean multitape DFA is more powerful than DFA? $\endgroup$
    – user19121278
    Jun 9 at 9:12
  • $\begingroup$ As per as my knowledge multitape DFA is equivalent to single DFA(I read on book). But here the things are contradicting means two tape with one way DFA is more powerful than DFA. So where I have missed to understand the things?? $\endgroup$
    – user19121278
    Jun 9 at 15:22
  • $\begingroup$ @user19121278 It is not clear to me how the book compares the single tape and multitape automata. The singletape defines a language, subset of some $\Sigma^*$. The multitape automata define relations, subset of some $\Sigma_1^*\times \dots \times\Sigma_k^*$. $\endgroup$
    – Hendrik Jan
    Jun 9 at 23:03
  • $\begingroup$ One thing tell single tape DFA which moves both direction is same powerful as classical DFA? But multitape Turing machine is equivalent to single tape Turing machine? Am I correct for both cases? $\endgroup$
    – user19121278
    Jun 9 at 23:09

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.