Me doy cuenta de que los autómatas de pushdown no deterministas pueden ser una mejora sobre los deterministas, ya que pueden "elegir" entre varios estados y hay algunos lenguajes libres de contexto que no pueden ser aceptados por un pushdown determinista.

Aún así, no entiendo cómo exactamente "eligen". Para palindormes, por ejemplo, cada fuente que encontré dice que el autómata "adivina" la mitad de la palabra. Qué significa eso?

Puedo pensar en varios significados posibles:

1. Entra en un estado al azar y, por lo tanto, puede no aceptar una palabra, que en realidad está en el idioma

2. De alguna manera funciona "de todas las maneras posibles", por lo que si el primero es incorrecto, prueba si alguno de los otros podría ser correcto

3. Hay algún mecanismo que no conozco, que elige el medio de la palabra y, por lo tanto, no es aleatorio, pero el autómata siempre encuentra el medio correcto.
   

Esto es solo un ejemplo; Lo que quiero saber es cómo funciona para cualquier autómata que tenga varios estados siguientes para un mismo estado antes.

En pocas palabras, el mecanismo es mágico. La idea del no determinismo es que simplemente sabe qué camino debe tomar para aceptar la palabra, y así sigue. Si hay varias formas, va una de ellas.

El no determinismo no se puede implementar como tal en hardware real. Lo simulamos utilizando técnicas como el retroceso. Pero es principalmente un dispositivo teórico, que puede usarse para simplificar la presentación de ciertos conceptos.

Para el palíndromo, puedes pensarlo de dos maneras. O hay un poder mágico que le permite a su máquina decir "este es el medio de la palabra, es hora de cambiar de empujar a hacer estallar", o después de leer cada letra, dice "Voy a bifurcar un nuevo proceso que esa letra es el medio de la palabra, y mira si encuentra que es un palíndromo. Luego, en este otro hilo, seguiré intentándolo, suponiendo que este no sea el medio de la palabra ".

Otra forma de pensarlo es como un paralelismo infinito. Entonces, un modelo equivalente sería que, en lugar de elegir una nueva ruta, intente simultáneamente ambas rutas, ramificando nuevos "procesos", teniendo éxito si alguno está en un estado final después de leer la palabra completa. Una vez más, esto no se puede construir con hardware real, pero se puede modelar sin determinismo.

Lo interesante del no determinismo es que, para los autómatas finitos y las máquinas de Turing, no aumenta en absoluto su poder computacional, solo su eficiencia.

La principal diferencia (en mi opinión) entre un autómata determinista y un autómata no determinista es que, para un autómata determinista, una palabra de entrada dada solo tiene una ruta a través de la máquina. En un autómata no determinista, una palabra de entrada dada puede tener múltiples rutas a través de la máquina (porque puede haber opciones en algunos puntos).

A la luz de esto, la condición para la aceptación de una palabra de entrada también necesita cambios para acomodar el hecho de que una palabra puede inducir varios caminos a través de la máquina. La definición habitual de aceptación para un autómata no determinista es la siguiente: para que una palabra sea aceptada por el autómata debe haber al menos un camino de aceptación inducido por esa palabra.

Esto lleva a la idea de un autómata "adivinando", si una palabra es aceptada por un autómata no determinista, tendemos a pensar que el autómata toma automáticamente las decisiones correctas para que (una de) la (s) ruta (s) de aceptación se sigue cuando esa palabra se presenta como entrada.

Lo que esto significa para los palíndromos es que el pda esencialmente tendrá dos modos: un modo de empuje donde empuja las letras actuales en la pila y un modo de estallido donde saca esas letras y las compara con la entrada. Esta máquina tendrá una transición vacía del estado de empuje al estado emergente que podrá seguir en cualquier punto de la palabra. Sin embargo, la máquina solo vaciará su pila y pasará a un estado de aceptación si ha leído un palíndromo y ha seguido la transición vacía en el medio del palíndromo. Como solo requerimos la existencia de un camino de aceptación, podemos decir que el autómata "adivina" dónde está la mitad de la palabra.

La idea del no determinismo es bastante simple: el autómata podría tener varios pasos siguientes en ciertas situaciones. El autómata acepta si hay alguna secuencia de pasos (¡podría haber varios!) Que conducen desde la configuración inicial a una de aceptación, rechaza solo si no existe tal secuencia.

Esto significa que "decide" qué paso dar a continuación en esas situaciones ambiguas. Una forma de hablar sobre esto es decir que selecciona mágicamente el siguiente paso "correcto" siempre (o uno, si hay varios pasos "correctos"). Otra forma de verlo es que, en tales situaciones, el cálculo del autómata se divide en varias copias, cada una siguiendo un camino.

En la práctica, esto puede implementarse retrocediendo, colocando alguna forma de etiqueta en los lugares donde se tomó la decisión, y regrese e intente la siguiente alternativa si la ruta actual no funciona. Esto generalmente se maneja por recursión. O complementando la información que el autómata tiene "legalmente" con información adicional (eso es lo que hace cuando muestra cómo funciona un autómata no determinista en la pizarra, mirando hacia adelante y descubriendo cuál de los pasos conduce al éxito).

"Adivinar" está directamente relacionado con nuestra interpretación existencial del no determinismo

En pocas palabras: esta idea que un autómata no determinista puede adivinar (o ser ayudado por un oráculo) está directamente relacionada con nuestra interpretación existencial del no determinismo. Es posible otra interpretación (quizás otras) donde "adivinar" no tendría sentido.

El no determinismo es extraño. Tenemos una forma de interpretarlo en la teoría de autómatas, pero no es a priori obvio cómo debemos hacerlo.

Puede parecer sorprendente, pero el no determinismo es una situación muy común. Cuando uno tiene que demostrar un teorema, dados los axiomas de alguna teoría matemática, el proceso es naturalmente no determinista. Es por eso que a menudo no sabemos qué hacer para resolver un problema, por ejemplo, para encontrar las soluciones de una ecuación de tercer grado, o probar algún teorema.

Hay muchas maneras de combinar lo que ya se conoce con las reglas de inferencia para obtener nuevos resultados. Y la situación suele ser la misma si intentamos reconstruir una prueba al revés del resultado.

Cuando intentamos resolver tal problema, tratamos de " adivinar " un camino en algún sistema de transición.

En realidad, no adivinamos, pero construimos en nuestra mente una estructura que organiza y / o simplifica el laberinto de posibilidades para que podamos ver nuestro camino a través de él. En algunos casos, la pregunta sigue un patrón identificado para el cual tenemos una forma estándar de encontrar (a veces? Generalmente? Siempre?) Una solución, y lo llamamos algoritmo.

Una técnica (generalmente costosa) que podemos usar es simplemente explorar completamente el laberinto: seguir todos los caminos, primero ampliándonos para evitar quedar atrapados en un subgrafo infinito. Esto es más o menos lo que se está haciendo al combinar todos los cálculos posibles de un autómata no determinista. Este cálculo derivado en cola de milano es en sí mismo determinista.

$DC$$A$$A$$A$

En realidad, podría haber diferentes formas de interpretar un cálculo no determinista . Afaik son todos consistentes, pero no entre sí.

$R$$w$

La idea de adivinar el reconocedor es solo una imagen tomada de nuestra propia forma de "adivinar" cómo encontrar ese árbol de pruebas. Pero la gran diferencia es que nuestros cerebros no son PDA. Son dispositivos mucho más complejos con la capacidad de explorar y mapear aproximadamente estructuras de transición para que podamos encontrar nuestro camino a través de ellas, lo que a veces percibimos como adivinanzas.

Esta interpretación del cálculo no determinista es lo que yo llamaría aceptación existencial , en referencia al hecho de que solo requiere la existencia de un único cálculo de aceptación. Corresponde a la detención existencial que presenté en otra respuesta .

Sin embargo, también se podría interpretar el no determinismo de manera universal como: se dice que un reconocedor acepta (universalmente) una entrada "w" si todos los cálculos posibles detienen y aceptan la entrada. Esta aceptación universal corresponde al concepto de detención universal introducido en la misma respuesta.

La aceptación universal y la detención universal parecen conducir a una comprensión autoconsistente del no determinismo. Por lo tanto, se podría hacer trabajo teórico con esa definición. Pero no es consistente con nuestra práctica habitual en muchas situaciones no deterministas, como una prueba de teorema, o en situaciones de la vida cotidiana. Cuando nos enfrentamos a un problema, solo queremos una forma de resolverlo, y luego no nos importa si otras formas tienen éxito o no (bueno, esto está un poco simplificado).

Si tenemos que reconocer un palíndromo, podemos adivinar midiendo la longitud y buscando el medio. El PDA no puede. Pero, como solo estamos interesados ​​en la existencia de una solución, siempre podemos pretender que puede ... si eso lo ayuda. O podemos considerar que tiene oráculos proporcionados por máquinas más inteligentes (¿nosotros?) Para ayudarlo. O incluso puede llamarlo magia, y pensar que lo es (después de todo, el cuantificador existencial es una especie de varita mágica). Si puede ayudar, lo hará. Si no se acepta la computación, no se utilizará ninguna ayuda.

Tenga en cuenta que esta idea de adivinar no tendría sentido en la interpretación de aceptación universal.