Preguntas sobre autómatas, gramáticas formales u otros modelos de computación que se relacionan específicamente con el uso del no determinismo. ¡No debe confundirse con aleatoriedad o ambigüedad!
Estaba pasando por la discusión sobre la pregunta ¿Cómo definir las máquinas cuánticas de Turing? y siento que la TM cuántica y la TM no determinista son lo mismo. Las respuestas a la otra pregunta no tocan eso. ¿Son estos dos modelos uno y el mismo? Si no, ¿Cuáles son las diferencias entre...
¿Qué diferencias y relaciones hay entre los algoritmos aleatorios y los algoritmos no deterministas? De Wikipedia UNA algoritmo aleatorio es un algoritmo que emplea un grado de aleatoriedad como parte de su lógica. El algoritmo generalmente utiliza bits aleatorios uniformes como entrada...
Sabemos que los DFA son equivalentes a los NFA en poder de expresividad; También hay un algoritmo conocido para convertir NFA a DFA (desafortunadamente ahora conozco al inventor de ese algoritmo), que en el peor de los casos nos da estados, si nuestro NFA tenía estados.2S2S2^SSSS Mi pregunta es:...
Un autómata es un modelo abstracto de una computadora digital. Las computadoras digitales son completamente deterministas; su estado en cualquier momento es únicamente predecible a partir de la entrada y el estado inicial. Cuando intentamos modelar sistemas reales, ¿por qué incluir el no...
Todos los autómatas finitos no deterministas pueden convertirse en autómatas finitos deterministas equivalentes. Sin embargo, un autómata finito determinista solo permite una sola flecha por símbolo que apunta desde un estado. Por lo tanto, sus estados deberían ser miembros del conjunto de estados...
La definición principal de Turing machine (TM), al menos en mi propio libro de texto de referencia (Hopcroft + Ullman 1979) es determinista. Por lo tanto, mi propia comprensión del problema de detención es principalmente para TM determinista, aunque soy consciente de que puede considerarse para...
Esta es una pregunta de seguimiento de esta . En una pregunta anterior sobre máquinas de estado exóticas , Alex ten Brink y Raphael abordaron las capacidades computacionales de un tipo peculiar de máquina de estado: los autómatas de min-montón. Pudieron demostrar que el conjunto de idiomas...
De Wikipedia sobre algoritmos aleatorios Hay que distinguir entre algoritmos que usan la entrada aleatoria para reducir el tiempo de ejecución esperado o el uso de memoria, pero siempre terminan con un resultado correcto en una cantidad limitada de tiempo, y algoritmos probabilísticos , que,...
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...
Sé que podemos minimizar los DFA al encontrar y fusionar estados equivalentes, pero ¿por qué no podemos hacer lo mismo con los NFA? No estoy buscando una prueba ni nada de eso, a menos que una prueba sea más fácil de entender. Solo quiero entender intuitivamente por qué la minimización de NFA es...
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...
Acabo de empezar a leer sobre teoría de la computación. Si comparamos cuál es más poderoso (al aceptar cadenas), ambos son iguales. ¿Pero qué hay de la eficiencia? DFA será rápido en comparación con NFA, ya que solo tiene una ventaja saliente y no habrá ambigüedad. Pero en el caso de NFA, tenemos...
Mañana es mi presentación y quiero aclarar mis conceptos ... He leído que en DFA, "Para cada estado, se debe definir la transición en todos los símbolos posibles (alfabeto)". ¿Es obligatorio para cada estado definir la transición en todos los símbolos posibles en DFA? Si no es así, ¿puede dar...
¿Qué diferencias hay entre las máquinas de Turing deterministas y no deterministas? Modelos diferentes pero equivalentes de NDTM. En particular, ¿cuál es esta frase de uso frecuente "adivinanza no determinista"? Cómo usarlo correctamente y ejemplos de uso incorrecto. Mi objetivo es crear una...
En la imagen a continuación, estoy tratando de averiguar qué es exactamente lo que esta NFA está aceptando. Lo que me confunde es el salto en .q 0ϵϵ\epsilonq0q0q_0 Si se ingresa un , ¿el sistema se mueve a y (el estado de aceptación)?q 0 q 1000q0q0q_0 q1q1q_1 Si se ingresa un , ¿se mueve el...
En el trabajo, se me ha encomendado la tarea de inferir cierta información sobre un lenguaje dinámico. Reescribo secuencias de declaraciones en letexpresiones anidadas , así: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x...
Mi libro de texto dice: "Definimos la función de la siguiente forma: f ( 1 ) = 2 y f ( i + 1 ) = 2 f ( i ) 1.2 . Tenga en cuenta que dado n , podemos encontrar fácilmente en O ( n 1.5 ) tiempo, el número i de tal manera que n se intercala entre f ( i ) y f ( i + 1f:N→Nf:N→Nf\colon...
Estoy aprendiendo cómo convertir NFA a DFA y quiero asegurarme de que lo estoy haciendo bien. Obviamente, retroceder en la otra dirección no es una cosa. ¿Alguien sabe de un algoritmo para verificar que un DFA es equivalente a un
Estoy trabajando en el Libro Sipser (2ª edición) y encontré este ejemplo, que no entiendo. En el libro dice que este NFA acepta la cadena vacía, ϵϵ\epsilon . ¿Podría alguien explicarme por qué este es el caso? Tengo entendido que ϵϵ\epsilon se moverá a q3q3q_3 que no es un estado de...
Deje una cadena de entrada como . Luego, si un NFA se encuentra actualmente en el estado r (y ha leído la entrada hasta el alfabeto w i ), antes de leer el siguiente símbolo de entrada, el NFA se divide en dos NFA, uno en el estado r y otro en s , si hay una transición del tipo r ϵ → s . Si hay un...