Me pregunto, ¿hay algún trabajo o investigación que trate con autómatas visiblemente pushdown, pero que permita que las palabras, en lugar de letras simples, sean empujadas a la pila. Alternativamente, una construcción que permita que los símbolos se presionen en las transiciones ϵϵ\epsilon podría...
Para un lenguaje L ⊆ Σ ^ * , defina la congruencia sintáctica ≡ de L como la menor congruencia en Σ ^ * que satura L , es decir: u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Ahora defina la equivalencia de Nerode como la siguiente congruencia correcta: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Sea [u] la clase...
Los autómatas finitos no ambiguos (UFA) son un tipo especial de autómatas finitos no deterministas (NFA). Un NFA se llama inequívoco si cada palabra tiene como máximo una ruta de aceptación.w ∈ Σ∗w∈Σ∗w\in \Sigma^* Esto significa .D FA ⊂ UFA ⊂ NFUNreFUN⊂UFUN⊂norteFUNDFA\subset UFA\subset...
Existe evidencia teórica de que la ingenua construcción de productos cartesianos para la intersección de los DFA es "lo mejor que podemos hacer". ¿Qué pasa con la concatenación de dos DFA? La construcción trivial implica convertir cada DFA en un NFA, agregar una transición épsilon y determinar el...
En la descripción formal de los Autómatas de empuje determinista, permiten movimientos , donde la máquina puede hacer estallar o empujar símbolos en la pila sin leer un símbolo de la entrada. Si estos movimientos no están permitidos, y la pila solo se puede modificar una vez después de cada símbolo...
Decimos que NFA MMM es constantemente ambiguo si existe k∈Nk∈Nk\in \mathbb{N} tal que cualquier palabra w∈Σ∗w∈Σ∗w\in \Sigma^* sea aceptada por 000 o (exactamente) caminos.kkk Si el autómata es constantemente ambiguo para , entonces se llama FA inequívoca (UFA).k = 1 MMMMk=1k=1k=1MMM Deje que...
Antecedentes: Dados dos autómatas finitos deterministas A y B, formamos el producto C dejando que los estados en C sean el producto cartesiano de los estados en A y los estados en B. Luego, elegimos las transiciones, el estado inicial y los estados finales para que el lenguaje sea aceptado por C...
¿Hay alguna jerarquía "agradable" conocida L0⊆L1⊆L2⊆…L0⊆L1⊆L2⊆…L_0 \subseteq L_1 \subseteq L_2 \subseteq \dots (puede ser finita) dentro de la clase de lenguajes regulares LLL ? Por bueno aquí, las clases en cada jerarquía capturan diferente expresividad / poder / complejidad. Además, la membresía...
Un autómata Xor no determinista (NXA) es sintácticamente un NFA, pero se dice que NXA acepta una palabra si tiene un número impar de rutas de aceptación (en lugar de al menos una ruta de aceptación en el caso de NFA). Es fácil ver que para un lenguaje regular finito , existe un NFA mínimo que no...
Deje que sea la familia de todos los idiomas más Σ que satisfacen la propiedad de bombeo de lenguajes regulares. A saber: para cada L ∈ L , hay una N ∈ N st cada palabra w ∈ L , | w | > N se puede escribir en la forma w = x y z donde: 1. | y | > 0 , 2. | x y | ≤ N , 3. x y i...
Let ser un lenguaje, entonces definimos la congruencia sintáctica como u ~ v : ⇔ ∀ x , y ∈ X * : x T y ∈ L ↔ x v y ∈ L y el cociente monoid X * / ~ L es llamado el monoide sintáctica de L .L⊆X∗L⊆X∗L \subseteq X^{\ast}u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈Lu∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u \sim v :\Leftrightarrow...
Estoy leyendo " Concatenación de idiomas regulares y complejidad descriptiva " de Galina Jiraskova, 2009 sobre la complejidad del estado resultante de la concatenación de dos idiomas regulares (por Galina Jiraskova), pero no puedo entender cuáles serían las implicaciones prácticas de la complejidad...
Lema: Suponiendo equivalencia eta tenemos eso (\x -> ⊥) = ⊥ :: A -> B. Prueba: ⊥ = (\x -> ⊥ x)por equivalencia eta y (\x -> ⊥ x) = (\x -> ⊥)por reducción bajo la lambda. El informe Haskell 2010, sección 6.2 especifica la seqfunción mediante dos ecuaciones: seq :: a -> b ->...
Reg⊆NC1Reg⊆NC1\mathsf{Reg} \subseteq \mathsf{NC^1}RegReg\mathsf{Reg}TC0⊈RegTC0⊈Reg\mathsf{TC^0} \not\subseteq \mathsf{Reg}Reg⊆TC0Reg⊆TC0\mathsf{Reg} \subseteq \mathsf{TC^0}NC1⊈TC0NC1⊈TC0\mathsf{NC^1}\not\subseteq\mathsf{TC^0}Reg⊈TC0Reg⊈TC0\mathsf{Reg} \not\subseteq \mathsf{TC^0} ¿Hay un...
Mientras enseñaba cómo implementar FSMs utilizando circuitos lógicos sincrónicos, noté una coincidencia intrigante: tanto en el mundo teórico de CS como en el mundo de la ingeniería eléctrica, el "estado" se denota típicamente (y el espacio de estado ). Primero pregunté sobre EESX , pero luego,...
Dado un autómata A finito (determinista o no determinista, no creo que esto tenga mucha importancia) y un umbral n , ¿acepta A una palabra que contenga como máximo n letras distintas? (Por k letras diferentes quiero decir que aabaa tiene dos letras distintas, a y b .) Mostré que este problema era...
En el marco de aprendizaje de autómatas de Angluin , un estudiante tiene como objetivo aprender un lenguaje regular L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* haciendo dos tipos de preguntas a su maestro: Consultas de palabras: dado w∈Σ∗w∈Σ∗w\in \Sigma^* , ¿es w∈Lw∈Lw\in L ? Consultas de equivalencia: dado un...
Entonces, tengo alrededor de 100-200 matrices booleanas cuadradas muy dispersas con longitud lateral ~ varias docenas, y necesito calcular su producto. Sé que si los multiplico en serie, el producto generalmente se mantendrá escaso en cada paso. ¿Hay algún algoritmo de producto de cadena de matriz...
¿Qué se sabe sobre la clase de idiomas reconocidos por autómatas finitos que tienen el mismo estado inicial y de aceptación? Este es un subconjunto adecuado de los idiomas regulares (ya que cada idioma contiene la cadena vacía), pero ¿qué tan débil es? ¿Existe una caracterización algebraica...
Estoy buscando una encuesta sobre los conceptos importantes en el campo de los autómatas cuánticos. He encontrado la teoría de los autómatas cuánticos: una revisión de Hirvensalo, pero parece demasiado sucinto para comprender el tema. ¿Existe una encuesta bastante completa sobre el tema de...