Autómata finito bidireccional

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

Un autómata finito determinista bidireccional ( AFD2 ) es una máquina abstracta , una versión generalizada del autómata finito determinista (AFD) que puede volver a procesar caracteres ya procesados. Al igual que en un AFD, existe un número finito de estados con transiciones entre ellos basadas en el 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, hacia la derecha o permanecerá en la misma posición. De forma equivalente, los AFD2 pueden considerarse máquinas de Turing de solo lectura sin cinta de trabajo, solo con una cinta de entrada de solo lectura.

Los autómatas finitos bidimensionales (AFD2) fueron introducidos en un artículo fundamental de 1959 por Rabin y Scott , ^{[ 1 ]} quienes demostraron que tienen una potencia equivalente a la de los autómatas finitos deterministas unidireccionales ( AFD1) . Es decir, cualquier lenguaje formal que pueda ser reconocido por un AFD2 puede ser reconocido por un AFD que solo examina y consume cada carácter en orden. Dado que los AFD son obviamente un caso especial de los AFD2, esto implica que ambos tipos de máquinas reconocen con precisión la clase de lenguajes regulares . Sin embargo, el AFD equivalente para un AFD2 puede requerir una cantidad exponencial de estados, lo que hace que los AFD2 sean una representación mucho más práctica para algoritmos en algunos problemas comunes.

Los autómatas finitos bidimensionales (2DFA) también son equivalentes a 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 puede incorporarse al estado de control finito mediante una construcción de producto (un estado para cada combinación de estado de la cinta de trabajo y estado de control).

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

• ${\displaystyle Q}$es el conjunto finito y 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 de extremo 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, 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}$

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

• Para todos los 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)}$

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 gira allí infinitamente. ^{[ 2 ]}

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 autómata finito no determinista (AFND) unidireccional estándar , un AFND bidireccional acepta una cadena si al menos uno de los cálculos posibles es de aceptación. Al igual que los AFND bidireccionales, los AFND bidireccionales también aceptan únicamente lenguajes regulares.

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

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

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

Los autómatas finitos bidireccionales y unidireccionales, 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 conlleva una explosión en el número de estados. Christos Kapoutsis ^{[ 3 ]} determinó que transformar un${\displaystyle n}$-Establecer un 2DFA a un DFA equivalente requiere${\displaystyle n(n^{n}-(n-1)^{n})}$estados en el peor de los casos. Si un${\displaystyle n}$-Si un 2DFA estatal o un 2NFA se transforma en un NFA, el número de estados requeridos en el peor de los casos es${\displaystyle {\binom {2n}{n+1}}=O\left({\frac {4^{n}}{\sqrt {n}}}\right)}$. Ladner , Lipton y Stockmeyer . ^{[ 4 ]} demostraron que un${\displaystyle n}$-El estado 2AFA se puede convertir en un DFA con${\displaystyle 2^{n2^{n}}}$estados. La conversión de 2AFA a NFA requiere${\displaystyle 2^{\Theta (n\log n)}}$estados en el peor de los casos, véase Geffert y Okhotin. ^{[ 5 ]}

Problema sin resolver en informática

¿Todos?${\displaystyle n}$-estado 2NFA tienen un equivalente${\displaystyle \operatorname {poly} (n)}$-¿estado 2DFA?

Más problemas sin resolver en informática

Es un problema abierto determinar si todo 2NFA puede convertirse en un 2DFA con un incremento polinómico en el número de estados. Este 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 ; véase Kapoutsis ^{[ 8 ]} para una relación precisa.

Los autómatas de barrido son 2DFA de un tipo especial que procesan la cadena de entrada realizando barridos alternos de izquierda a derecha y de derecha a izquierda, girando solo en los marcadores de extremo. 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${\displaystyle 2^{n}}$estados.

El concepto de 2DFA fue generalizado en 1997 a la computación cuántica por John Watrous en "On the Power of 2-Way Quantum Finite State Automata", en el que demuestra que estas máquinas pueden reconocer lenguajes no regulares y, por lo tanto, son más potentes que los DFA. ^{[ 10 ]}

Un autómata de pila que puede moverse en cualquier dirección en su cinta de entrada se llama autómata de pila bidireccional ( 2PDA ); ^{[ 11 ]} fue 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 de pila bidireccionales deterministas ( 2DPDA ) y no deterministas ( 2NPDA ); Gray, Harrison e Ibarra (1967) investigaron las propiedades de cierre de estos lenguajes. ^{[ 15 ]}