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...
El objetivo es crear DFA a partir de una expresión regular y usar "Exp. Regular> NFA> Conversión de DFA" no es una opción. ¿Cómo debería uno hacer eso? Le hice esta pregunta a nuestro profesor, pero él me dijo que podemos usar la intuición y amablemente se negó a dar ninguna explicación....
Quiero convertir una expresión regular ingresada por el usuario en un NFA para que luego pueda ejecutar el NFA en una cadena con fines coincidentes. ¿Cuál es la máquina mínima que se puede usar para analizar las expresiones regulares? Supongo que debe ser un autómata push down porque la presencia...
Entonces, dados dos DFA, ¿es el problema de encontrar si generan el mismo idioma un problema decidible? Ya sé que la igualdad de dos CFL no es decidible pero ¿qué pasa con la igualdad de dos DFA? Teniendo en cuenta que la mayoría de los problemas con los DFA son decidibles, ¿esto también es...
Tenía la impresión de que nuestras computadoras, siendo finitas, en última instancia no son más poderosas que las máquinas de estado finito (extraordinariamente grandes). Sin embargo, las máquinas de Turing con límites lineales también son finitas, pero parece que los lenguajes regulares son...
Esta puede ser una pregunta tonta. Parece claro que una FSA, dado que es finita, solo puede contar el número de símbolos en su cadena de entrada hasta un número limitado por el número de sus estados. Pero ahora supongamos que equipamos a la FSA con capacidades de salida (por ejemplo, impresión)....
Me preguntaba, ya que una∗a∗a^* es en sí mismo un lenguaje sin estrellas, ¿existe un lenguaje normal que no sea un idioma sin estrellas? ¿Podrías dar un ejemplo? (de wikipdia ) Lawson define lenguajes sin estrellas como: Se dice que un lenguaje regular no tiene estrellas si puede describirse...
¿Existe un autómata celular (en 2D) que simula una fuerza entre partículas?1/r1/r1/r Más específicamente, me gustaría saber si es posible, con reglas de actualización estrictamente locales, que dos objetos (definidos dentro del modelo) se atraigan entre sí con una fuerza de , donde es la distancia...
Tengo un problema simple de hacer un DFA que acepte todas las entradas que comienzan con letras dobles (aa, bb) o terminan con letras dobles (aa, bb), dado que es el conjunto alfabético del lenguaje dadoΣ={a,b}Σ={a,b}\Sigma =\{a, b\} Traté de resolverlo de una manera indirecta: Generando una...
Si entiendo correctamente, NFA tiene el mismo poder expresivo que las expresiones regulares. A menudo, leer expresiones regulares equivalentes de NFA es fácil: traduce ciclos a estrellas, uniones como alternativas, etc. Pero qué hacer en este caso: [ fuente ] Los ciclos superpuestos hacen que...
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...
Minimizar los autómatas finitos deterministas (DFA) es un problema que se ha estudiado a fondo en la literatura, y se han propuesto varios algoritmos para resolver el siguiente problema: Dado un DFA , calcule un DFA mínimo correspondiente que acepte el mismo lenguaje que . La mayoría de estos...
Dados dos conjuntos de cadenas sobre el alfabeto , ¿podemos calcular el autómata determinista de estado finito (DFA) más pequeño de modo que y ?A , BUN,siA,BΣΣ\SigmaMETROMETROMA ⊆ L ( M)UN⊆L(METRO)A \subseteq L(M)L ( M) ⊆ Σ∗∖ BL(METRO)⊆Σ∗∖siL(M) \subseteq \Sigma^*\setminus B En otras palabras,...
¿Cómo puedo construir un ejemplo de un DFA que tiene estados donde el NFA equivalente tiene estados? Obviamente, el conjunto de estados del DFA debe contener todos los subconjuntos del conjunto de estados del NFA, pero no sé cómo comenzar. ¿Alguna sugerencia para ponerme en el camino correcto?...
El algoritmo de Brzozowski se puede extender a los autómatas de Moore, pero su complejidad temporal es exponencial en general. ¿Hay algún otro algoritmo para minimizar los autómatas de Moore? ¿Cuáles son los tiempos de ejecución de estos algoritmos si los
Estoy buscando una especialización en Informática Teórica; específicamente, estoy interesado en la teoría de la complejidad y la teoría probabilística de autómatas. Al graduarme en un año, ¿qué cursos avanzados de matemáticas (como la teoría de Galois o el análisis armónico, por ejemplo) crees que...
Describa un idioma normal que no pueda ser aceptado por ningún DFA que tenga solo tres estados. No estoy realmente seguro de por dónde empezar con esto y me preguntaba si alguien podría darme algunos consejos o sugerencias. Entiendo que el lema de bombeo se puede usar para probar que un idioma...
Hay una manera de realizar un análisis difuso (acepta cadenas incluso con errores tipográficos a una cierta distancia de edición), con un DFA y un Autómata Levenshtein construido en tiempo de ejecución de la palabra de entrada. ¿Se puede hacer algo similar con un analizador Earley? Me resulta...
Estaba jugando con la demostración de Google Blocky's Maze , y recordé la vieja regla de que si quieres resolver un laberinto, solo mantén la mano izquierda en la pared. Esto funciona para cualquier laberinto conectado de forma simple y puede implementarse mediante un transductor finito. Deje que...
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