Tengo esta pregunta [algo graciosa] en mente. ¿Por qué el autómata finito no determinista se llama no determinista mientras definimos las transiciones para las entradas? Bueno, aunque hay transiciones múltiples y épsilon , están definidas, lo que significa que la máquina es determinista para esas transiciones. Lo que significa que es determinista.
finite-automata
nondeterminism
Madhusoodan P
fuente
fuente
Respuestas:
"Determinista" significa "si coloca el sistema en la misma situación dos veces, se garantiza que tomará la misma decisión en ambas ocasiones".
"No determinista" significa "no determinista", o en otras palabras, "si coloca el sistema en la misma situación dos veces, podría o no tomar la misma decisión en ambas ocasiones".
Un autómata finito no determinista (NFA) puede tener múltiples transiciones fuera de un estado. Esto significa que hay múltiples opciones para lo que podría hacer en esa situación. No está obligado a elegir siempre el mismo; en una entrada, podría elegir la primera transición, y en otra entrada podría elegir la misma transición.
Aquí puede pensar en "situación" como "en qué estado se encuentra la NFA, junto con qué símbolo se lee a continuación de la entrada". Incluso cuando ambos son iguales, un NFA aún puede tener múltiples transiciones coincidentes que se pueden sacar de ese estado, y puede elegir arbitrariamente cuál tomar. Por el contrario, un DFA solo tiene una transición coincidente que se puede tomar en esa situación, por lo que no tiene otra opción: siempre seguirá la misma transición siempre que esté en esa situación.
fuente
Tome este autómata por ejemplo, es un NFA y acepta la cadena . Para ser más pedante, acepta cadenas que terminan en 10 .0110 10
Para ver que solo necesitamos verificar si alcanza un estado de aceptación.
Ahora en la línea roja había otra posibilidad, es decir, al leer el segundo , podría permanecer en q 0 y luego permanecer en q 0 al leer el último 0 . Los autómatas no tienen memoria, por lo que no hay forma de 'guardar' un estado y verificar más tarde si mi cadena termina con 101 q0 0 q0 0 0 0 10 , es como si este NFA adivinando si la cadena termina con antes de bifurcarse a un estado aceptable. El no determinismo aquí es tomar muchas decisiones y siempre tomar las correctas.10
Es más fácil construir un NFA que construir un DFA, lo bueno es que ambos son equivalentes .
fuente
La función de transición de un NFA especifica las transiciones permitidas en cualquier momento. Podría haber más de una opción, y la NFA elige una transición no determinista con el objetivo de llegar a un estado de aceptación.
Tal vez deberías esperar hasta que aprendas sobre las máquinas Turing no deterministas. El no determinismo significa lo mismo en ambos casos.
fuente
Comience con un autómata finito. Tiene estados y estados de aceptación y transiciones.
Ahora, dele más de una regla de transición de cada estado y diga que acepta si existe un conjunto de reglas de transición seleccionadas después del hecho que conducen al estado de aceptación dada una cadena de entrada.
Una vez que tenga su cadena de entrada, hay un conjunto fijo de transiciones concretas y afirma que pasa (una a la vez) para aceptar esa cadena. Pero las transiciones que elige solo se eligen al final de la cadena . Mientras se lee la cadena, no se determina qué ruta tomar.
No es determinista. Puede elegir su camino a través del gráfico después de darle todo el problema, no mientras lee la entrada.
Ahora, formalizamos esto de manera diferente a este experimento mental, pero esto te motiva por qué obtuvo ese nombre.
Esto explica cómo obtuvo el nombre en primer lugar. Sí, puede modelar NDFA de una manera completamente determinista, pero los nombres son adhesivos . Una vez que haya llamado a algo Bob, hay un costo de comunicación para cambiarle el nombre a algo más, ya que nadie sabe de qué está hablando cuando lo llama Alice.
fuente
Desde wikipedia , la mejor manera de pensar en esto es comenzar con máquinas deterministas de estados finitos (DFA). Para un DFA, cada transición está determinada únicamente por el estado actual y el símbolo de entrada que se procesará. Las máquinas de estados finitos no deterministas (NFA) son simplemente lo que obtienes cuando relajas esta regla de determinismo para permitir que las transiciones no se definan de manera única. Es lo que obtienes cuando eliminas la regla de determinismo de los DFA.
fuente
NFA y DFA se utilizan para (entre otras cosas) reconocer ciertas cadenas.
El autómata finito no determinista funciona como si tuviera influencia en sus decisiones: puede "elegir" seguir un camino o no.
En la imagen de arriba, cuando se trata de la cadena "00111", observe que al encontrar el primer "1", hay dos formas posibles de seguir. Uno puede permanecer en "p" o ir a "q". Si el autómata se moviera a la "q", no aceptaría la cadena (ya que no hay bordes saliendo de la "q"). Pero la cadena puede ser aceptada por este autómata yendo a la "q" con solo el último 1, mientras permanece en "p" para todo lo demás (y eso es lo que está sucediendo).
NFA hace que parezca que los autómatas "sabían" lo que está por venir, y elige en consecuencia.
Por supuesto que no. DFA y NFA son equivalentes en términos de potencia (puede reducir NFA a DFA y hacer que DFA (probablemente) sea más simple con el uso de NFA), pero NFA es útil, ya que permite definir los mismos idiomas que DFA manteniendo los gráficos mucho más corto y más legible.
No hay nada al azar allí. La parte no determinista pone énfasis en el hecho de que hay alguna "elección" que tomar, pero la verdad es que el autómata no toma ninguna decisión.
fuente
Bueno, aquí está la mezcla de algunos contenidos del libro [Introducción a los idiomas y autómatas formales de Peter Linz 4E] y mi comprensión.
Considere un programa de juego donde la máquina necesita tomar la decisión para el próximo movimiento [digamos de tres en raya]. Como hay varios movimientos posibles, elegimos de manera determinista cada movimiento y evaluamos el movimiento y optamos por el mejor. Aunque el proceso de selección fue determinista y hubo muchos movimientos posibles, el movimiento final realizado fue uno único y se eligió como el mejor movimiento mientras se ocultaban todos los cálculos de movimientos probados del oponente. [Aquí asumimos que el proceso de evaluación de cada posible movimiento estaba oculto para el oponente].
Por lo tanto, solo se hizo una elección y se le da al oponente una ilusión tal que el movimiento no fue determinista.
Bueno, si aún no está convencido al preguntar que el mejor movimiento fue el producto de algunos cálculos deterministas, entonces debe considerar la máquina que realiza movimientos perfectamente aleatorios (puede ser pérdida de máquina pero es un NFA).
fuente