Autômato finito determinístico de dois sentidos

Na ciência da computação, em particular na teoria dos autômatos, um autômato finito bidirecional (em inglês: two-way finite automaton) é um autômato finito que pode 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^{[nota 1]}

Formalmente, um two-way deterministic finite automaton pode ser descrito pela seguinte 8-tupla: ${\displaystyle M=(Q,\Sigma ,L,R,\delta ,s,t,r)}$ onde

• ${\displaystyle Q}$ é o conjunto finito não vazio de estados
• ${\displaystyle \Sigma }$ é o conjunto finito não vazio do alfabeto de entrada
• ${\displaystyle L}$ é o marcador de fim de fita esquerdo
• ${\displaystyle R}$ é o marcador de fim de fita direito
• ${\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{left,right\}}$
• ${\displaystyle s}$ é o estado inicial
• ${\displaystyle t}$ é o estado final
• ${\displaystyle r}$ é o estado de rejeição

Além disso, as seguintes condições também devem ser satisfeitas:

• Para todo ${\displaystyle q\in Q}$

${\displaystyle \delta (q,L)=(q^{\prime },right)}$ para algum ${\displaystyle q^{\prime }\in Q}$

${\displaystyle \delta (q,R)=(q^{\prime },left)}$ para algum ${\displaystyle 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 ${\displaystyle \sigma \in \Sigma \cup \{L\}}$

${\displaystyle \delta (t,\sigma )=(t,R)}$

${\displaystyle \delta (r,\sigma )=(r,R)}$

${\displaystyle \delta (t,R)=(t,L)}$

${\displaystyle \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",^[1] 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.^[2]

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);^[3] foi estudado por Hartmanis, Lewis, and Stearns (1965),^[4] Aho, Hopcroft, Ullman (1968)^[5] e Cook (1971)^[6] caracterizada as propriedades de fecho dessa classe de linguagens.^[7]

Notas e referências

Notas

1. Essa definição foi tirada das notas da aula CS682 (Theory of Computation) por Dexter Kozen da Universidade de Stanford

Referências

1. Rabin, M. O.; Scott, D. (abril de 1959). «Finite Automata and Their Decision Problems». IBM Journal of Research and Development (2): 114–125. ISSN 0018-8646. doi:10.1147/rd.32.0114. Consultado em 30 de outubro de 2023 
2. Kondacs, A.; Watrous, J. (1997). «On the power of quantum finite state automata». IEEE Comput. Soc: 66–75. ISBN 978-0-8186-8197-4. doi:10.1109/SFCS.1997.646094. Consultado em 30 de outubro de 2023 
3. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. [S.l.]: Addison-Wesley. ISBN 0-201-02988-X  Here: p.124; this paragraph is omitted in the 2003 edition.
4. Hartmanis, J.; Lewis II, P.M.; Stearns, R.E. (1965). «Hierarchies of Memory Limited Computations». Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design. Ann Arbor, MI, USA: [s.n.] pp. 179–190. doi:10.1109/FOCS.1965.11 
5. Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1968). «Time and Tape Complexity of Pushdown Automaton Languages». Information and Control. 13 (3): 186-206. doi:10.1016/s0019-9958(68)91087-5 
6. Cook, S.A. (1971). «Linear Time Simulation of Deterministic Two-Way Pushdown Automata». Proc. IFIP Congress. [S.l.]: North Holland. pp. 75–80 
7. Jim Gray, Michael A. Harrison, Oscar H. Ibarra (1967). «Two-Way Pushdown Automata». Information and Control. 11 (1–2): 30–70. doi:10.1016/s0019-9958(67)90369-5  !CS1 manut: Nomes múltiplos: lista de autores (link)

• Hing Leung. Two-Way Deterministic Finite Automata.