# Autômato finito determinístico de dois sentidos

Em Ciência da Computação, em particular em Teoria dos Autômatos, um autômato é chamado two-way se é permitido reler sua entrada.

## Autômato finito determinístico de dois sentidos

Um two-way deterministic finite automaton (2DFA) é uma máquina abstrata, uma versão generalizada de autômato finito determinístico (do inglês "DFA") que pode visitar caracteres já processados. Como em um DFA, existem um número finito de estados com transições entre eles baseado no caractere atual, mas cada transição é também rotulada com um valor indicando se a máquina irá mover sua posição na entrada para a esquerda, direita, ou ficar na mesma posição. Equivalentemente, 2DFAs podem ser visto como Máquinas de Turing de somente leitura sem fita de trabalho, apenas uma fita de entrada de somente leitura.
2DFAs podem ser mostradas como tendo poder equivalente às DFAs, qual seja, qualquer linguagem formal que pode ser reconhecida por uma 2DFA pode ser reconhecida por um DFA que somente examina e consome cada caractere em ordem. Desde que DFAs são obviamente um caso especial de 2DFAs, isso implica que ambas máquinas reconheçam precisamente o conjunto de linguagens regulares. No entanto, o DFA equivalente a um 2DFA pode ter exponencialmente mais estados, fazendo 2DFAs uma representação muito mais prática para algoritmos para algum problema comum. Eles são também equivalentes à Máquinas de Turing de somente leitura que usa apenas uma quantidade constante de espaço em sua fita de trabalho, desde que qualquer quantidade constante de informação pode ser incorporada dentro do estado de controle finito via uma produção constante (um estado para cada combinação do estado da fita de trabalho e estado de controle).

## Descrição Formal

Formalmente, um two-way deterministic finite automaton pode ser descrito pela seguinte 8-tupla: $M=(Q,\Sigma ,L,R,\delta ,s,t,r)$ onde
* $Q$ é o conjunto finito não vazio de estados
* $\Sigma$ é o conjunto finito não vazio do alfabeto de entrada
* $L$ é o marcador de fim de fita esquerdo
* $R$ é o marcador de fim de fita direito
* $\delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{left,right\}$
* $s$ é o estado inicial
* $t$ é o estado final
* $r$ é o estado de rejeição
Além disso, as seguintes condições também devem ser satisfeitas:
* Para todo $q\in Q$
    $\delta (q,L)=(q^{\prime },right)$ para algum $q^{\prime }\in Q$
    $\delta (q,R)=(q^{\prime },left)$ para algum $q^{\prime }\in Q$
Diz que deve haver alguma transição possível quando o ponteiro no alfabeto chega ao fim.
* Para todos os símbolos $\sigma \in \Sigma \cup \{L\}$
    $\delta (t,\sigma )=(t,R)$
    $\delta (r,\sigma )=(r,R)$
    $\delta (t,R)=(t,L)$
    $\delta (r,R)=(r,L)$
Diz que uma vez que o autômato chega ao estado de aceitação ou rejeição, ele fica lá para sempre e o ponteiro vai para símbolo mais à direita e fica lá infinitamente.

## Autômato finito quântico de dois sentidos

O conceito de 2DFAs, originado by Rabin e Scott em seu 1959 trabalho seminal "Finite automata and their decision problems", foi em 1997 generalizado para computação quântica by John Watrous's "On the Power of 2-Way Quantum Finite State Automata", em que ele demonstra que essas máquinas podem reconhecer linguagens não regulares e então são mais poderosas do que DFAs.

## Autômato com Pilha de dois sentidos

Um autômato com pilha que tem permissão para mover-se de que qualquer maneira em sua fita de entrada é chamada autômato com pilha de dois sentidos (2PDA); foi estudado por Hartmanis, Lewis, and Stearns (1965), Aho, Hopcroft, Ullman (1968) e Cook (1971) caracterizada as propriedades de fecho dessa classe de linguagens.