Quiero saber si el siguiente problema es decidible: Instancia: un NFA A con n estados Pregunta: ¿Existe algún número primo p tal que A acepte alguna cadena de longitud p. Creo que este problema es indecidible, pero no puedo probarlo. El decisor puede tener fácilmente un algoritmo para determinar...
Dado un alfabeto , ¿cuántos idiomas regulares diferentes puede aceptar un autómata finito no determinista de estados?Σ={a,b}Σ={a,b}\Sigma = \{ a,b \}nnn Como ejemplo, consideremos . Luego tenemos configuraciones de transición diferentes y configuraciones de estado inicial y final diferentes, por...
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...
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...
Estoy estudiando lenguajes formales y sistemas de bases de producción (sistemas de bases de reglas) y estoy un poco confundido acerca de por qué estas dos palabras "producción" y "regla" significan lo mismo en tantos contextos en informática. En inglés no parecen significar lo mismo. No soy...
Soy un programador con control sobre los autómatas, pero no sobre la lógica. Leí en periódicos que los dos están estrechamente relacionados. Los autómatas finitos deterministas (DFA), los autómatas de árbol y los autómatas visiblemente pushdown están todos relacionados con la lógica monádica de...
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...
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...
Me pregunto, ¿cuál es la complejidad temporal de determinar el vacío para los DFA de 2 vías? Es decir, autómatas finitos que pueden moverse hacia atrás en su cinta de entrada de solo lectura. Según Wikipedia, son equivalentes a los DFA, aunque el DFA equivalente podría ser exponencialmente más...
Si no es así, ¿qué significa cuando para algún estado qqq y algún símbolo unaaa , δ( q, Un )δ(q,a)\delta(q, a) no
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....
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)....
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...
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...
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...
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,...
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...
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...
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...
O al menos generar un conjunto de cadenas que una NFA acepta, para que pueda alimentarlo a la otra NFA. Si hago una búsqueda en cada ruta de la NFA, ¿funcionará? Aunque eso llevará mucho