Autómata finito de dos vías

Tipos de autómatas finitos en la teoría de autómatas

En informática , en particular en teoría de autómatas , un autómata finito bidireccional es un autómata finito al que se le permite releer su entrada.

Autómata finito determinista bidireccional

Un autómata finito determinista bidireccional ( 2DFA ) es una máquina abstracta , una versión generalizada del autómata finito determinista (DFA) que puede revisar caracteres ya procesados. Al igual que en un DFA, hay un número finito de estados con transiciones entre ellos en función del carácter actual, pero cada transición también está etiquetada con un valor que indica si la máquina moverá su posición en la entrada hacia la izquierda, la derecha o permanecerá en la misma posición. De manera equivalente, los 2DFA pueden verse como máquinas de Turing de solo lectura sin cinta de trabajo, solo una cinta de entrada de solo lectura.

Los 2DFAs fueron introducidos en un artículo seminal de 1959 por Rabin y Scott ^[1] , quienes demostraron que tienen un poder equivalente a los DFA unidireccionales . Es decir, cualquier lenguaje formal que pueda ser reconocido por un 2DFA puede ser reconocido por un DFA que solo examina y consume cada carácter en orden. Dado que los DFA son obviamente un caso especial de 2DFA, esto implica que ambos tipos de máquinas reconocen precisamente la clase de lenguajes regulares . Sin embargo, el DFA equivalente para un 2DFA puede requerir exponencialmente muchos estados, lo que hace que los 2DFA sean una representación mucho más práctica para algoritmos para algunos problemas comunes.

Los 2DFA también son equivalentes a las máquinas de Turing de solo lectura que utilizan solo una cantidad constante de espacio en su cinta de trabajo, ya que cualquier cantidad constante de información se puede incorporar al estado de control finito a través de una construcción de producto (un estado para cada combinación de estado de cinta de trabajo y estado de control).

Descripción formal

Formalmente, un autómata finito determinista bidireccional se puede describir mediante la siguiente tupla de 8 : donde ${\displaystyle M=(Q,\Sigma ,L,R,\delta ,s,t,r)}$

• ${\displaystyle Q}$es el conjunto finito, no vacío de estados
• ${\displaystyle \Sigma }$es el conjunto finito y no vacío de símbolos de entrada
• ${\displaystyle L}$es el marcador final izquierdo
• ${\displaystyle R}$es el marcador final correcto
• ${\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow Q\times \{\mathrm {left,right} \}}$
• ${\displaystyle s}$es el estado inicial
• ${\displaystyle t}$es el estado final
• ${\displaystyle r}$es el estado de rechazo

Además, también deben cumplirse las dos condiciones siguientes:

• A pesar de ${\displaystyle q\in Q}$

${\displaystyle \delta (q,L)=(q^{\prime },\mathrm {right} )}$Para algunos ${\displaystyle q^{\prime }\in Q}$

${\displaystyle \delta (q,R)=(q^{\prime },\mathrm {left} )}$Para algunos ${\displaystyle q^{\prime }\in Q}$

Dice que debe haber alguna transición posible cuando el puntero llega a cualquiera de los extremos de la palabra de entrada.

• Para todos los símbolos ^{[ aclaración necesaria ]} ${\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)}$

Dice que una vez que el autómata alcanza el estado de aceptación o rechazo, permanece allí para siempre y el puntero va al símbolo más a la derecha y recorre ese ciclo infinitamente. ^[2]

Autómata finito no determinista de dos vías

Un autómata finito no determinista bidireccional (2NFA) puede tener múltiples transiciones definidas en la misma configuración. Su función de transición es

• ${\displaystyle \delta :Q\times (\Sigma \cup \{L,R\})\rightarrow 2^{Q\times \{\mathrm {left,right} \}}}$.

Al igual que un análisis de nodo unidireccional estándar , un análisis de nodo doble acepta una cadena si al menos uno de los cálculos posibles la acepta. Al igual que los análisis de nodo doble, los análisis de nodo doble también aceptan solo lenguajes regulares.

Autómata finito alterno de dos vías

Un autómata finito alterno bidireccional (2AFA) es una extensión bidireccional de un autómata finito alterno (AFA). Su conjunto de estados es

• ${\displaystyle Q=Q_{\exists }\cup Q_{\forall }}$dónde . ${\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }$

Los estados en y se denominan existenciales o universales . En un estado existencial, un 2AFA elige de manera no determinista el siguiente estado como un NFA y lo acepta si al menos uno de los cálculos resultantes lo acepta. En un estado universal, un 2AFA se mueve a todos los siguientes estados y lo acepta si todos los cálculos resultantes lo aceptan. ${\displaystyle Q_{\exists }}$ ${\displaystyle Q_{\forall }}$

Compensaciones en la complejidad del estado

Los autómatas finitos unidireccionales y bidireccionales, deterministas y no deterministas y alternantes, aceptan la misma clase de lenguajes regulares. Sin embargo, transformar un autómata de un tipo en un autómata equivalente de otro tipo implica un aumento repentino del número de estados. Christos Kapoutsis ^[3] determinó que transformar un 2DFA de -estado en un DFA equivalente requiere estados en el peor de los casos. Si un 2DFA de -estado o un 2NFA se transforma en un NFA, el número de estados requerido en el peor de los casos es . Ladner , Lipton y Stockmeyer . ^[4] demostraron que un 2AFA de -estado se puede convertir en un DFA con estados. La conversión de 2AFA a NFA requiere estados en el peor de los casos, consulte Geffert y Okhotin. ^[5] ${\displaystyle n}$ ${\displaystyle n(n^{n}-(n-1)^{n})}$ ${\displaystyle n}$ ${\displaystyle {\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)}$ ${\displaystyle n}$ ${\displaystyle 2^{n2^{n}}}$ ${\displaystyle 2^{\Theta (n\log n)}}$

Problema sin resolver en informática :

¿Cada 2NFA de estado tiene un 2DFA de estado equivalente? ${\displaystyle n}$ ${\displaystyle \operatorname {poly} (n)}$

(más problemas sin resolver en informática)

Es un problema abierto si cada 2NFA se puede convertir en un 2DFA con solo un aumento polinomial en el número de estados. El problema fue planteado por Sakoda y Sipser ^[6] , quienes lo compararon con el problema P vs. NP en la teoría de la complejidad computacional . Berman y Lingas ^[7] descubrieron una relación formal entre este problema y el problema abierto L vs. NL ; consulte Kapoutsis ^[8] para una relación precisa.

Autómatas de barrido

Los autómatas de barrido son 2DFA de un tipo especial que procesan la cadena de entrada haciendo barridos alternos de izquierda a derecha y de derecha a izquierda, girando solo en los marcadores finales. Sipser ^[9] construyó una secuencia de lenguajes, cada uno aceptado por un NFA de n estados, pero que no es aceptado por ningún autómata de barrido con menos de estados. ${\displaystyle 2^{n}}$

Autómata cuántico finito bidireccional

El concepto de 2DFAs fue generalizado en 1997 a la computación cuántica por John Watrous en "Sobre el poder de los autómatas cuánticos de estados finitos bidireccionales", en el que demuestra que estas máquinas pueden reconocer lenguajes no regulares y por lo tanto son más poderosas que los DFAs. ^[10]

Autómata pushdown bidireccional

Un autómata pushdown al que se le permite moverse en cualquier dirección en su cinta de entrada se llama autómata pushdown bidireccional ( 2PDA ); ^[11] ha sido estudiado por Hartmanis, Lewis y Stearns (1965). ^[12] Aho, Hopcroft, Ullman (1968) ^[13] y Cook (1971) ^[14] caracterizaron la clase de lenguajes reconocibles por autómatas pushdown bidireccionales deterministas ( 2DPDA ) y no deterministas ( 2NPDA ); Gray, Harrison e Ibarra (1967) investigaron las propiedades de cierre de estos lenguajes. ^[15]

Referencias

1. Rabin, Michael O.; Scott, Dana (1959). "Autómatas finitos y sus problemas de decisión". Revista IBM de Investigación y Desarrollo . 3 (2): 114–125. doi :10.1147/rd.32.0114.
2. Esta definición ha sido tomada de las notas de la clase CS682 (Teoría de la computación) de Dexter Kozen de la Universidad de Stanford.
3. Kapoutsis, Christos (2005). "Eliminación de la bidireccionalidad de los autómatas finitos no deterministas". En J. Jedrzejowicz, A. Szepietowski (ed.). Fundamentos matemáticos de la informática . MFCS 2005. Vol. 3618. Springer. págs. 544–555. doi :10.1007/11549345_47.
4. Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Autómatas de pila y pushdown alternos". Revista SIAM de informática . 13 (1): 135–155. doi :10.1137/0213010. ISSN  0097-5397.
5. Geffert, Viliam; Okhotin, Alexander (2014). "Transformación de autómatas finitos alternos bidireccionales en autómatas no deterministas unidireccionales". Fundamentos matemáticos de la informática 2014. Apuntes de clase en informática. Vol. 8634. págs. 291–302. doi :10.1007/978-3-662-44522-8_25. ISBN 978-3-662-44521-1. ISSN  0302-9743.
6. Sakoda, William J.; Sipser, Michael (1978). No determinismo y tamaño de autómatas finitos bidireccionales . STOC 1978. ACM. págs. 275–286. doi : 10.1145/800133.804357 .
7. Berman, Piotr; Lingas, Andrzej (1977). Sobre la complejidad de los lenguajes regulares en términos de autómatas finitos . Vol. Informe 304. Academia Polaca de Ciencias.
8. Kapoutsis, Christos A. (2014). "Autómatas bidireccionales versus espacio logarítmico". Teoría de sistemas informáticos . 55 (2): 421–447. doi :10.1007/s00224-013-9465-0.
9. Sipser, Michael (1980). "Límites inferiores del tamaño de los autómatas de barrido". Revista de Ciencias de la Computación y de Sistemas . 21 (2): 195–202. doi :10.1016/0022-0000(80)90034-3.
10. John Watrous . Sobre el poder de los autómatas cuánticos de estados finitos de dos vías. CS-TR-1997-1350. 1997. pdf
11. John E. Hopcroft; Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 978-0-201-02988-8.Aquí: p.124; este párrafo se omite en la edición de 2003.
12. J. Hartmanis; PM Lewis II, RE Stearns (1965). "Jerarquías de cálculos con memoria limitada". Proc. 6.° Simposio anual IEEE sobre teoría de circuitos de conmutación y diseño lógico . págs. 179-190.
13. Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1968). "Complejidad temporal y de cinta de lenguajes de autómatas pushdown". Información y control . 13 (3): 186–206. doi : 10.1016/s0019-9958(68)91087-5 .
14. SA Cook (1971). "Simulación en tiempo lineal de autómatas deterministas de dos vías". Actas del Congreso IFIP . Holanda Septentrional. págs. 75–80.
15. Jim Gray; Michael A. Harrison; Oscar H. Ibarra (1967). "Autómatas pushdown bidireccionales". Información y control . 11 (1–2): 30–70. doi :10.1016/s0019-9958(67)90369-5.